POJいろいろ8/1

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>を使ったら、>>を> >にしろや、TLEするやで散々。
あと半分全列挙って言われなかったら解法思いつかなかったかも。

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;
}