はまやんはまやんはまやん

hamayanhamayan's blog

Shift and Flip [AtCoder Grand Contest 019 D]

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