Codeforces Round #641 Div. 2 E - Binary Subsequence Rotation

問題: Problem - E - Codeforces

公式解説: Editorial — Codeforces Round #651 - Codeforces

問題概要

長さ $n (1 \leq n \leq 10^6)$ の 01 文字列 $s. t$ が与えられる。この文字列 $s$ に次の操作を繰り返し， $t$ と等しくする。

• 操作: $s$ の部分文字列を選び，右に回転させる。(1110100→1100110)

最低何回操作すれば良いか。

解法概要

まず前提として，$s$ と $t$ の $i$ 文字目をそれぞれ $s_i$, $t_i$ とすると，

• $s_i = 0$ かつ $t_i = 1$ となる $i$ の数
• $s_i = 1$ かつ $t_i = 0$ となる $i$ の数

は互いに等しくなければ，$s$ と $t$ を等しくすることはできない (出力がすべき値が $-1$ になる)。 以下はこの2つが等しいことを前提に考える。

1回の操作でできるだけ$s_i \neq t_i$ となる $i$ を減らすには，010101... (または 101010...) となるように $s$ の部分列を選び，その部分列について1回操作を適用すれば良い (この発想がすごい……本番で全く思いつかなかった)。 ここでは，$s_i = 0$ かつ $t_i = 1$ となる $i$ の数と$s_i = 1$ かつ $t_i = 0$ となる $i$ の数は等しいとしているので，1回の操作用の部分列 0 と 1 を同数ずつ採用している限りは片方が足りなくて 0101... (1010...) が作れないということはないはず。

したがって，$s_i \neq t_i$ となる $s_i$ が 0101... (1010...) という形の部分列いくつ分からできるかを計算すればよい。これは，$s_i$ を前から見ていき，$s_i \neq t_i$ のときに最後が 0 となる部分列の数と最後が 1 となる部分列の数をそれぞれ更新しながら数えれば良い。ソースコード参照。

ソースコード

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;
    string s, t;
    cin >> s >> t;

    int s_cnt = 0, t_cnt = 0;
    for(int i=0;i<n;++i) {
        s_cnt += int(s[i] - '0');
        t_cnt += int(t[i] - '0');
    }
    if(s_cnt != t_cnt) {
        cout << -1 << endl;
        return 0;
    }

    vector<int> v(2, 0); // v[0]: 最後が 0 になる部分列の数, v[1]: 最後が 1 になる部分列の数
    for(int i=0;i<n;++i) {
        if(s[i] == t[i]) continue; // 等しければ操作を適用する必要はない
        int j = int(s[i] - '0');
        if(v[1-j]) { // 今見ている数字と異なる (= 0 と 1 を交互にするときに，今見ている数字を追加可能な) 文字列があるか？
            --v[1-j];
            ++v[j];
        } else {
            ++v[j]; // 末尾に今見ている数字を追加可能な文字列がなければ，文字列を増やす
        }
    }

    cout << v[0]+v[1] << endl;
}

所感

問題を見た瞬間にこれ無理なやつだと思ったんですが，後からやってみるとそうでもないし面白いですね。