簡単なバグを埋め込んでしまった...

問題へのリンク

問題概要

長さ $N$ の "0" と "1" のみからなる 2 つの文字列 $S, T$ が与えられる。 $S$ に対して以下の操作を繰り返し行うことで $T$ に一致させることができるかどうかを判定し、可能ならば最小回数を求めよ。

$S$ 中の "01" を "10" にする
$S$ 中の "11" を "00" にする

制約

$1 \le N \le 5 \times 10^{5}$

考えたこと (僕の解法)

想定解法とちょっと違う方法で解いた。とりあえず、 $S$ 中の 1 の個数を $a$ 、 $T$ 中の 1 の個数を $b$ とすると、直ちに次のことが言える。

$a \lt b$ の場合は不可能
$a$ と $b$ の偶奇が不一致の場合は不可能

実際には、これらの条件を満たしていても不可能な場合もある。たとえば以下の場合。

2
10
01

1 は左にスライドさせることができるが、右にスライドさせることはできない。それを踏まえると、 $S$ から $T$ への対応は下図のような形式になることは言える (下図は最適解ではない)。

$S$ 中の "1" と "1" の対消滅は、もともと隣接している "1" 同士に限ってよい
対消滅後に残った "1" が左から順に、の "1" に左から順にそれぞれ対応していく
- このとき、 $S$ 側の index の方が小さくなることはないようにする

このように考えると DP したくなるのだけど、実際には Greedy に解ける。 $T$ の中の "1" を左から順に見ていくことにする。現在考えている $T$ の "1" の index を $t$ とする。

仮にの中に残っている "1" の最左の index がよりも小さい限りは次の作業を行う
- $S$ の左 2 個の "1" を対消滅させる (2 個以上残っていなかったら不可能)
- このときのコストは、その 2 個の "1" の index の差となる
上記の作業後に中に残っている最左の "1" (index をとする) を、に対応させる
- このときのコストは、 $s - t$ で与えられる (1 個以上残ってなかったら不可能)
最後に $S$ 中に "1" が残っている場合は、左から 2 個ずつ対消滅させていく

計算量は $O(N)$ となる。

コード

ある index i に対して S[i] = 1、T[i] = 1 となっていた場合の $S$ 中の index i を削除する作業を失念するバグに苦しんだ。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    string S, T;
    cin >> N >> S >> T;
    auto solve = [&]() -> long long {
        deque<long long> A, B;
        for (int i = 0; i < N; ++i) {
            if (S[i] == '1') A.push_back(i);
            if (T[i] == '1') B.push_back(i);
        }
        if (A.size() < B.size() || (B.size() - A.size()) % 2 == 1) return -1;
        auto twopop = [&]() -> long long {
            long long res = A[1] - A[0];
            A.pop_front(), A.pop_front();
            return res;
        };
        long long res = 0;
        for (auto id : B) {
            while (!A.empty() && A[0] < id) {
                if (A.size() < 2) return -1;
                res += twopop();
            }
            if (A.empty()) return -1;
            res += A[0] - id;
            A.pop_front();
        }
        if (A.size() % 2 == 1) return -1;
        while (!A.empty()) res += twopop();
        return res;
    };
    cout << solve() << endl;
}

解法 (2)：想定解法

操作の前後で "1" の総和のパリティが不変であることを思うと、

「 $S$ や $T$ を累積 XOR をとった世界で考える」

という変換が有効そうな直感が働く気がしてきた。そうすると操作は

"01" を "11" にする
"10" を "00" にする

と言い換えられる。これらは統一的に

「 $S_{i}$ と $S_{i+1}$ が相異なるとき、 $S_{i}$ を $S_{i+1}$ に揃える」

と言える。つまり、0 と 1 の扱いが対象的になっている。左から見ていったときに

$S_{i} \neq T_{i}$ となっていたとき、
$S$ の $i$ 番目以降ではじめて $S_{j} \neq S_{j+1}$ となるような $j$ を、 $i$ のところまで持ってくる

というふうにすれば OK。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main() {
    int N;
    string S, T;
    cin >> N >> S >> T;
    auto solve = [&]() -> long long {
        vector<int> A(N+1, 0), B(N+1, 0);
        for (int i = 0; i < N; ++i) {
            A[i+1] = A[i] ^ (S[i]-'0');
            B[i+1] = B[i] ^ (T[i]-'0');
        }
        long long res = 0;
        int s = 0;
        for (int t = 0; t <= N; ++t) {
            chmax(s, t);
            if (A[s] == B[t]) continue;
            while (s+1 <= N && A[s] == A[s+1]) ++s;
            if (s == N) return -1;
            ++s;
            res += s-t;
        } 
        return res;
    };
    cout << solve() << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 049 B - Flip Digits (緑色, 600 点)

問題概要

制約

考えたこと (僕の解法)

コード

解法 (2)：想定解法