http://agc019.contest.atcoder.jp/tasks/agc019_d
解説
http://agc019.contest.atcoder.jp/submissions/1549295
公式解説放送の副読本です。
基本的な考え方は解説放送の通り。
isng関数は不可能であるか判定する関数。
不可能な場合はBが全て0でAが全て0でない場合は不可能。
f(d)関数はAを右にd回スライドさせて終了するときの最小コストを返す。
A[i]はA[(i+d)%N]に移動するため、A[(i+d)%N]!=B[i]であるものだけ考えていく。
ここで[i,i+d]の範囲のBに1があれば移動する過程で変換すればいい。
もし1が無ければ、左か右かに移動して1で追加で変換する必要がある。
左に移動して一番近い1に移動するための距離をL, 右に移動して一番近い1に移動するための距離をRとする。
すると、「A[(i+d)%N]!=B[i]かつB[i,i+d]に1が無い」ときの(L,R)の組においてどちらかを被覆するような範囲[A,B]でA+Bが最小のものを求めれば良いことになる。
これは解説放送にもあった部分問題であるが、関数gでそれを解いている。
部分問題
Lについて降順ソートする。
ここで前半と後半に分かれて考える。
[0,i]ではR側を被覆して、[i+1,n-1]ではL側を被覆する場合、L[i]+max(R[0],...,R[i])だけの範囲が必要となる。
後半部分は累積で最大を取っていけばいいため、この問題はソート分のO(NlogN)で解ける。
後は、解説放送でDの範囲を[0,2N]に変形して解いていたやつを[-2N,2N]に対応するために、AとBを反転して同じアルゴリズムで解くと、逆のスライドも計算することができてAC
#define INF INT_MAX/2 string A, B; int N; //--------------------------------------------------------------------------------------------------- int isng() { if (count(B.begin(), B.end(), '1')) return 0; if (count(A.begin(), A.end(), '1')) return 1; return 0; } //--------------------------------------------------------------------------------------------------- int g(vector<pair<int, int>> &v) { sort(v.begin(), v.end(), greater<pair<int, int>>()); int res = INF, rmax = 0; fore(p, v) { res = min(res, p.first + rmax); rmax = max(rmax, p.second); } res = min(res, rmax); return res; } //--------------------------------------------------------------------------------------------------- int pre[2020], post[2020], sm[2020]; int f(int d) { int firs = -1; int last = 0; rep(i, 0, N) { if (firs < 0 && B[i] == '1') firs = i; if (B[i] == '1') last = i; } int p = last; rep(i, 0, N) { pre[i] = p; if (B[i] == '1') p = i; } p = firs; rrep(i, N - 1, 0) { post[i] = p; if (B[i] == '1') p = i; } sm[0] = 0; if (B[0] == '1') sm[0] = 1; rep(i, 1, N) { if (B[i] == '1') sm[i] = sm[i - 1] + 1; else sm[i] = sm[i - 1]; } vector<pair<int, int>> v; int res = 0; rep(i, 0, N) { if (A[i] == B[(i + d) % N]) continue; res++; int a = i, b = (i + d) % N; int ss = -1; if (a <= b) { ss = sm[b]; if (a) ss -= sm[a - 1]; } else { ss = sm[N - 1]; if (a) ss -= sm[a - 1]; ss += sm[b]; } if (ss) continue; int k = pre[i]; int L = i - k; if (L < 0) L += N; int l = post[(i + d) % N]; int R = l - (i + d) % N; if (R < 0) R += N; v.push_back({ L, R }); } res += 2 * g(v) + d; return res; } //--------------------------------------------------------------------------------------------------- int solve() { int ans = INF; rep(d, 0, N * 2) ans = min(ans, f(d)); return ans; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> A >> B; N = A.length(); if (isng()) { printf("-1\n"); return; } int ans = INF; ans = solve(); reverse(A.begin(), A.end()); reverse(B.begin(), B.end()); ans = min(ans, solve()); cout << ans << endl; }