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"; }
こういう問題を素早く解けるようになるといいね。