3185
http://poj.org/problem?id=3185
普通に端から反転させるだけ…と思ったが、端の場合分けで反転の回数カウントしていなくてWA生やしまくった。
1222
http://poj.org/problem?id=1222
これも端を決めて反転するだけ。反転は決めることが本質。
2100
http://poj.org/problem?id=2100
さすがにしゃくとりやるだけ。Two Pointersってしゃくとりのことだったのか…
3977
http://poj.org/problem?id=3977
半分全列挙。コードが煩雑になりがち。long longにabsが使えなくてCE。scanf("%d",a)としてWA。cin使いたい。
2549
http://poj.org/problem?id=2549
最大を求めよって文を見逃す。map
あと半分全列挙って言われなかったら解法思いつかなかったかも。
2566
http://poj.org/problem?id=2566
累積和をとるという発想が出てこなかった。区間和は累積和。NをN+1にしたらWAになったし尺取りは範囲が難しい。
2566のコード
int N; int Q; int A[MAX_N]; pl S[MAX_N]; ll _abs(ll a) { return a > 0 ? a : -a; } pair<ll, pi> solve2(ll m) { int r = -1; ll res = linf; pi at; rep(i, 0, N) { while(S[r + 1].fst - S[i].fst <= m && r != N - 1) { r++; } if(_abs(res - m) > _abs(S[r].fst - S[i].fst - m) && r != i) { res = S[r].fst - S[i].fst; at = pi(S[r].sec, S[i].sec); } if(_abs(res - m) > _abs(S[r + 1].fst - S[i].fst - m)) { res = S[r + 1].fst - S[i].fst; at = pi(S[r + 1].sec, S[i].sec); } } if(at.fst > at.sec) swap(at.fst, at.sec); return make_pair(res, at); } void solve(int M) { S[0] = pi(0, 0); rep(i, 0, N) { S[i + 1].fst = S[i].fst + A[i]; S[i + 1].sec = i + 1; } sort(S, S + N + 1); pair<ll, pi> r1 = solve2(M); printf("%lld %d %d\n", r1.fst, r1.sec.fst + 1, r1.sec.sec); } int main() { while(true) { scanf("%d%lld", &N, &Q); if(N == 0 && Q == 0) break; rep(i, 0, N) scanf("%d", &A[i]); while(Q--) { int a; scanf("%d", &a); solve(a); } } return 0; }