AtCoder ABC083(ARC088) D - Wide Flip (500)

【ℹ️ この記事は K-Shoot Mania 譜面制作チーム TapeStop100 のアドベントカレンダー企画，TapeStop100 Advent Calendar 2019 の 2 日目の記事です。】

おはようございます，TapeStop100 の Мороже です🛰️*1 ボム兵（と本当はつまぶきなんだけど，知名度がボム兵に圧倒的に負けているのであまり知られていない）アイコンでボム兵を持ち歩いてるのでボム兵の人とか呼ばれていたりすることもあります。*0
TapeStop100 内ではパッケージの譜面制作やウェブサイト制作などを担当しています。普段は自然言語とかポップンとかやってます。（僕についての情報は @Morojenium やツイフィールでどうぞ）

今回の Advent Calendar*2 ではかなり最初の方の 2 日目を担当する流れとなったので，TP100 の初期からのメンバーとして K-Shoot Mania の譜面制作についての話をしていきたいと思います(⋈◍＞◡＜◍)。✧♡…………裏話: もともとこの記事は Advent Calendar とは関係なく作られたもので，下書きまで書いた段階でちょうどみかんくんから Advent Calendar 作ろうぜ！って話が出たのでノリで出したものです，決してこんな記事を建てるためだけに真面目に内容を書いたわけではない（ほんまか？）（ほんまです）

←いい画像ですね！記事中に一切登場しない点を除けば

AtCoder ABC083 D - Wide Flip の問題概要

問題URL: https://atcoder.jp/contests/abc083/tasks/arc088_b

$1$ 列に並んだ $N$ 枚のオセロの駒があり，コマの黒白の状態が $0$ と $1$ からなる文字列で与えられる。（ただし $0$ が白， $1$ が黒）
「 $K$ 個以上の連続するコマを flip する操作を $0$ 回以上行なう」ことによって，全てのコマを白にできるような最大の $K$ の値を求めよ。

お気持ちと方針

公式 editorial では $O(N)$ の解法が説明されていますが，個人的にあまり直感的ではなかった $\land$ $O(N\log N)$ の方針が検索サイトで調べた限りでは載っていなかったので，ここでは $O(N\log N)$ 解法を紹介します。

まず，
$f(K) :=$ 長さ $K$ 以上の区間で flip を $0$ 回以上行うことでコマを全て白にできるか？
と定義します。ここで操作についてよく考えると， $K$ を固定したときに長さが $K$ 以上であるような区間を flip することができるので，ある $K$ で条件（すべて白にする）が達成可能であれば， $K-1$ でも条件が達成可能です（ $\because$ 長さ $K-1$ の区間操作を使わなくても， $K$ 以上の長さの区間の操作のみで条件を達成できる）。
つまり帰納的にある $K=X$ で条件が達成可能なら， $K = 1, 2, ..., X$ でも達成可能で，この $X$ の最大値を求めよというのが問題文の意味するところです。
ところで $X$ の最大値 $M$ について， $K = 1, 2, ..., M$ なら $f(K) = {\rm true}$ であり， $K = M+1, M+2, ...$ なら $f(K) = {\rm false}$ となります。すなわち $f(K)$ には単調性があります。ここから， $f(K)$ を二分探索し真偽値の境目を求める（二分法）という方針が思い浮かびます。

単調性のある真偽値関数を二分探索するのはわりと典型的な方針で，蟻本 3-1 で取り上げられていたり，ABC にもその方針で解ける問題とかがちょくちょくあったりします。計算量から逆算すると，二分探索部分の計算量が $O(\log N)$ なので，だいたい $O(N)$ で真偽判定を実行できればいいことがわかります。
というわけで，この問題は「ある $K$ について $f(K)$ を $O(N)$ で求める」という問題に還元されたので，ここからは操作について詳しく考察します。

具体例として $N = 7, K \geq 6$ の場合に条件を達成できる盤面を列挙して眺めます（ここで， $K \geq X$ は区間の長さが $X$ 以上の操作が可能という意味です）。
たとえば以下の盤面は $0$ 回以上の操作によって全て白にできます（白にできる盤面はこれで全部です）:

○○○○○○○
●○○○○○○
○○○○○○●
●○○○○○●
●●●●●●●
○●●●●●●
●●●●●●○
○●●●●●○

これ系の問題*3で「全部白（全部黒）」という状態は言いかえれば，「各隣り合うコマにおいて色の異なっているものが 1 つもない」ということであり，条件を達成する手順は「隣り合うコマで色の異なっている部分を flip によって同じ色にする手順」となります。たとえば長さがピッタリ $K = 6$ の区間で flip する場合は，以下の図で仕切りを入れた前後の色の異なりを操作によって解消することができます:

○|○○○○○|○

長さがピッタリ $K = 5$ の区間ならこう:

○○|○○○|○○

$K \geq 5$ のときは:

○|○|○○○|○|○

逆に言えば，仕切りの入っていない真ん中の部分は色の異なりを解消することができないので，ざっくりと「真ん中の部分に色の異なりがある $\Leftrightarrow$ 条件が達成不可能」ということがわかります。
具体例で見てみましょう。たとえば $K \geq 5$ のときこれは全部白にできますが:

●○●●●○●

これは無理です（真ん中の ●○● がどうやっても解消できないので）:

○○●○●○○

ということで，「ある $K$ について条件が達成可能 $\Leftrightarrow$ 真ん中の部分に色の異なりがない」ということになり，これは $O(N)$ で調べられるのでこの問題が $O(N\log N)$ で解けました。
細かいところは提出コードに説明をまかせます:

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

string s;
int n;

bool possible( int k ){
    bool res = true;
    for( int i = n-k; i < k-1; ++i ){
        if( s[i] != s[i+1] ) res = false;
    }
    return res;
}

int main(){
    cin >> s;
    n = s.size();
    int ok = 1;
    int ng = n+1;
    while( ng-ok > 1 ){
        int mid = (ok+ng)/2;
        if( possible(mid) ){
            ok = mid;
        } else {
            ng = mid;
        }
    }
    cout << ok << endl;
}

改善

この方法はアプローチとしては比較的自然でしたが*4，よくよく考えると盤面は常に constant なのに盤面を何度も線形走査しているあたり，明らかに無駄がありそうです*5。
実は，「真ん中の部分に色の異なりがない $\Leftrightarrow$ ある $K$ について条件が達成可能」なので，色がずっと同じであるような真ん中の範囲さえ分かれば $K$ の最大値もすぐに分かります。

たとえばこの盤面:

●●○●○○○○○●

この場合，「真ん中の範囲」は縦棒で囲まれたところです:

●●○●|○○|○○○●

なので答えは $K = 6$ です。

実際に調べるには，左右からじわじわと区間を狭めていって，色の異なりが現れなくなるポイント（つまり，最後に色が異なっていた場所）を記録すれば良さそうです。結局，盤面全体を眺めればよいので， $O(N)$ でこの問題は解けました。

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

int main(){
    string s; cin >> s;
    int n = s.size();
    int l = 0, r = n-1;
    int a = 0, b = n;
    while( l < r ){
        if( s[l] != s[l+1] ) a = l+1;
        if( s[r-1] != s[r] ) b = r;
        ++l; --r;
    }
    cout << min(n-a, b) << endl;
}

コード中の l, r はコマを表す添字で，a, b は範囲の仕切りを表す添字と解釈するとたぶんわかりやすいです。

まとめという名のゴリ押しな終わり方（なんだお前）

長くなったのでまとめます。要するに譜面制作をしている途中でネタ切れになり必死になって思いつく配置は，上で述べたとおり普段から置いているリトリで音を破壊して置く縦連とかの手癖から離れているぶん，むしろ譜面に彩りを加えられるということです。時間をかけて譜面制作をするのは大変ですが，そのぶん高い完成度と自身の創作力につながるので，可能な限り粘っていきましょう。あれ，この記事何かがおかしいような……
そんなちっさい声で曖昧なこと言っててもわかんないだろ。もっと，ほら，具体的に……　←でも隠すこともそんなにないよね　←確かに
今回は以上です。これからも TapeStop100 と僕の差分譜面たちをよろしくお願いします！🛰️

執筆: Мороже auch bekannt als bG9█Z███m████...

TapeStop100 Advent Calendar 2019 День 2
vorh: TapeStop100とはいったい何なのか？【アドベントカレンダー１日目】｜洛葉みかん / Lac-Ba｜note
näch: TP100限界語録・闇の一面【アドベントカレンダー3日目】｜洛葉みかん / Lac-Ba｜note

*0: でも自作でないキャラを背負うのって責任が伴うので実は考え直したほうが良いのかもとか思ってもみたり。好きなキャラにネガティブなイメージがつくのは自分が傷つくよりも苦しいので……

*1:これはパラボーの絵文字です（パラボーかわいくない？）

*2:英語の calendar，ドイツ語では Kalender なのでいつもスペルが怖くなる……英語側ではどうやら光沢機の意味の calender との衝突を避けるために綴りが変更されたっぽい？

*3:学生コンC - Cell Inversion とか

*4:本番中の提出だと O(N) も O(NlogN) もありました

*5:ABC144 D - Water Bottle が同じような例で，想定解は二分法のようですが水の量は一定なので二分探索する必要がありません