AtCoder Grand Contest 019D: Shift and Flip

http://agc019.contest.atcoder.jp/tasks/agc019_d

なんとなくの解法はわかるけど詰めるのが結構難しいと思う。

Sをiだけ右にshiftした場所でTと一致させることを考える。
移動したSとTを比較したとき、Si == 1 && Ti == 0のとき、その場でSiを0に反転させることができない。ほかの場合はその場で反転できるorそもそも一致しているなので、このような場合のみについて考えることにする。

Siを0にするためには、Tj == 1を満たす場所で反転を行う必要がある。何回shiftすればTj == 1となる場所と対応するかを右shift左shiftについて配列を持っておく。

各iについて右shiftまたは左shiftを選べばよいことになるが、shift0から順番に見ていくと右右…右左左…左の時が最適になることがわかる。右左右なら左を右にしても結果は変わらないからだ。
なので右から左に変えるところをn回試せば求めるべき値が求まる。

int N;
string S, T;
int A[MAX_N], B[MAX_N];
int C[MAX_N], M[MAX_N];

void solve() {
	cin >> S >> T;
	N = sz(S);
	fill(A, A + N, inf);
	rep(i, 0, N) {
		rep(j, 0, N) {
			if(T[(i + j) % N] == '1') {
				A[i] = min(A[i], j);
				B[i] = max(B[i], j);
			}
		}
	}
	if(A[0] == inf) {
		bool ok = true;
		rep(i, 0, N) if(S[i] == '1') ok = false;
		if(ok) cout << 0 << "\n";
		else cout << -1 << "\n";
		return;
	}
	int res = inf;
	rep(i, 0, N) {
		int tmp = 0;
		fill(C, C + N, inf);
		rep(j, 0, N) {
			if(T[(i + j) % N] != S[j]) {
				tmp++;
				if(S[j] == '1') MIN(C[A[j]], B[j]);
			}
		}
		fill(M, M + N + 1, inf);
		int mi = -1, mx;
		rer(j, N, 0) {
			M[j] = min(M[j + 1], C[j]);
			if(C[j] != inf) MAX(mi, j);
		}
		mx = M[0];
		if(mx == inf) MIN(res, tmp + min(i, N - i));
		else {
			MIN(res, tmp + mi + min(abs(mi - i), N - abs(mi - i))); 
			MIN(res, tmp + N - mx + min(abs(mx - i), N - abs(mx - i))); 
		}
		rep(j, 0, N) {
			if(C[j] != inf) {
				mi = j; mx = M[j + 1];
				if(mx == inf) continue;
				MIN(res, tmp + mi + N - (mx - mi) + min(abs(mx - i), N - abs(mx - i)));
				MIN(res, tmp + N - mx + N - (mx - mi) + min(abs(mi - i), N - abs(mi - i)));
			}
		}
	}
	cout << res << "\n";
}

こういう問題を素早く解けるようになるといいね。