AtCoder Grand Contest 019 D - Shift and Flip

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

問題概要

0と1のみからなる同じ長さの文字列A, Bが与えられる。以下の操作を何度か行ってAを変化させていったとき、AをBに一致させることができるか判定せよ。また可能な場合は最小の操作回数を求めよ。

  • 操作1. Aを左に1文字回転させる
  • 操作2. Aを右に1文字回転させる
  • 操作3. B[i] = 1であるようなiをひとつ選び、A[i]を反転する

|A| <= 2000

解法

結論:先頭に来るインデックス×左に回す回数、先頭に来るインデックス×右に回す回数の組合せを全探索する。O(|A|^2 log|A|).

まずAの中で最終的に先頭にくるインデックスiを固定する。こうするとすべてのインデックスについて反転操作が必要かどうかが決定できる(=操作3にかかる回数も一意に決定できる)。あとは要反転のインデックスがすべてB=1のインデックスに当たるように回転操作を繰り返し、最後にiが先頭に来るように回転操作をすればよい。

ありうる回転操作は「左に回す→右に回す→iが先頭になるように回す」もしくは「右に回す→左に回す→iが先頭になるように回す」しかない。愚直にやると左に回す回数×右に回す回数で全探索をかけることになるが、それだとO(N3)になってしまう。しかしうまくやると左に回す回数を決めた時点で右に回す回数は決定できる(逆も)。前計算としてすべてのインデックスについて「左右それぞれについて最低何回回すとB[i]=1のインデックスにたどり着けるか」を記録しておく。これをL, Rとおくと、まず左にn回回した場合はLがn以下のインデックスをすべて反転済とみなせる。あとは残ったインデックスのうちRが最大のものを選び、その分だけ右に回すようにする。最後に先頭の位置が最初決めたところになるよう回す。これは(L, R)のペアで配列をとってソートしたりなんだりすればO(NlogN)でできる。右→左のパターンも同様。これらを先頭固定のO(N)と合わせてO(|A|^2 log|A|).

感想

本番中に大筋で正しい方針にはたどり着いたが通せず。終了後もバグ取りとか細部の詰めが必要ですぐには通せなかった。実装力大事

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
     
     
void main() {
    auto A = readln.chomp.map!(x => x == '1').array;
    auto B = readln.chomp.map!(x => x == '1').array;
    auto N = A.length.to!int;
     
    if (A.any && !B.any) {
        writeln(-1);
        return;
    }
     
    auto L = new int[](N);
    auto R = new int[](N);
     
    foreach (i; 0..N) {
        foreach (j; 0..N) {
            if (B[((i-j)%N+N)%N]) {
                L[i] = j;
                break;
            }
        }
        foreach (j; 0..N) {
            if (B[(i+j)%N]) {
                R[i] = j;
                break;
            }
        }
    }

     
    int ans = 1 << 29;
     
    foreach (i; 0..N) { // A[i]を先頭にする
        int flip = 0;
        auto LR = new Tuple!(int, int)[](N);
     
        foreach (j; 0..N) {
            int k = (i + j) % N;
            if (B[j] != A[k]) {
                flip++;
                LR[j] = tuple(L[k], R[k]);
            } else {
                LR[j] = tuple(0, 0);
            }
        }

        // 左 -> 右
        LR.sort!"a[0] < b[0]";
     
        auto r_max = new int[](N + 1);
        r_max[N] = 0;
     
        for (int j = N - 1; j >= 0; j--) {
            r_max[j] = max(LR[j][1], r_max[j+1]);
        }

        foreach (j; 0..N) {
            int left = LR[j][0];
            int right = r_max[j+1] + left;
            int pos = i - left + right;
            pos = (pos % N + N) % N;
            pos = min(pos, N - pos);
            ans = min(ans, left + right + pos + flip);
            debug {writeln([i, j, left, right, pos]);}
        }


        // 右 -> 左
        LR.sort!"a[1] < b[1]";
     
        auto l_max = new int[](N + 1);
        l_max[N] = 0;
     
        for (int j = N - 1; j >= 0; j--) {
            l_max[j] = max(LR[j][0], l_max[j+1]);
        }

        foreach (j; 0..N) {
            int right = LR[j][1];
            int left = l_max[j+1] + right;
            int pos = i - left + right;
            pos = (pos % N + N) % N;
            pos = min(pos, N - pos);
            ans = min(ans, left + right + pos + flip);
            debug {writeln([i, j, left, right, pos]);}
        }        
    }
     
    ans.writeln;
}