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

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

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

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

問題概要

長さ  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" が左から順に、 T の "1" に左から順にそれぞれ対応していく
    • このとき、 S 側の index の方が小さくなることはないようにする

f:id:drken1215:20201115034748p:plain

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


  • 仮に  S の中に残っている "1" の最左の index が  t よりも小さい限りは次の作業を行う
    •  S の左 2 個の "1" を対消滅させる (2 個以上残っていなかったら不可能)
    • このときのコストは、その 2 個の "1" の index の差となる
  • 上記の作業後に  S 中に残っている最左の "1" (index を  s とする) を、 t に対応させる
    • このときのコストは、 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;
}