好き。実装が軽いのも良い。

問題

$0,1$の列が与えられる。 $1$秒ごとに、列の中で$1,0$となっている部分を全て反転させる。 何秒で変化がなくなるか。

解法

sortである。 最左の$1$(あるいは最右の$0$でもよい)がいつ動き終わるかを答えればよい。

単純に目的地との距離を考えたいが、移動先を別の$1$が塞ぎ途中でしばらく移動できない時間がある。これを考える。 初期状態で隣に$1$が連続していると、その分だけ移動の開始が遅れる。 また$0$を挟んだ少し先に移動の開始が遅い$1$があると、これに追い付きしばらく停滞することがある。 この停滞(移動開始後に発生する)を、移動開始時間を送らせる、という形で扱えばよい。

実装

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
template <class T> bool setmax(T & l, T const & r) { if (not (l < r)) return false; l = r; return true; }
using namespace std;
int main() {
    string s; cin >> s; s += 'M';
    int n = s.length();
    vector<int> a(n); repeat (i,n) a[i] = s[i] == 'M';
    int ans = 0;
    int swaps = 0, wall = 0;
    repeat (i,n) {
        if (a[i]) {
            wall = max(0, wall - 1);
            swaps += 1;
        } else {
            if (swaps) {
                setmax(ans, wall + swaps);
                wall += 1;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

実験用

#!/usr/bin/env python3
s = input()
n = len(s)
# s = [int(c == 'M') for c in s]
s = list(map(int,s))
print(*s)
while s != list(sorted(s)):
    t = list(s)
    for i in range(n-1):
        if s[i] > s[i+1]:
            t[i], t[i+1] = s[i+1], s[i]
    s = t
    print(*s)