ARC088 D Wide Flip

atcoder.jp

所感

500も結構自力ACできる

問題概要

0と1からなる文字列Sが与えられる。以下の操作を繰り返してSの要素をすべて0にできるような最大の整数Kを求めよ。

長さK以上の区間を選択し、0と1を反転させる。  

取った方針

Sの長さ|S| をLとおく。
手元で実験をすると、左右L - K 個の数は任意にできることがわかる。(理由:K + 1個の区間を反転させてから任意にしたい場所以外のK個を反転させればよい)
残った2K-L 個の値は一度に反転させられなければならないので、すべて同じ数である必要がある。
すべて同じ数であるかどうかはO(L)で判定できるので、Kを二分探索すればO(LlogL)で解ける。

正しい方針

左右L - K 個の数は任意にできることはそのまま用いる。
0と1の変化点に注目すると、上記の方法で変化点をひとつづつ潰すことができるので、端から一番近い変化点を潰せるKを選択する。

得られた知見

・めぐる式二分探索
・区間を反転させる -> 自由にできる(できない)場所に注目

解くのに必要な要素

・区間を反転させる -> 自由にできる(できない)場所に注目

周辺調査によって得られた知見

特になし