ABC124 D - Handstand
解法
1...(または0...)が連続しているとき、連続している部分は1つにまとめてしまいたいので、ランレングス圧縮のように、連続して何個続いているか、という情報に置き換えておきます。
今回の問題の場合、0...が続いている区間を個以下1...に反転して、作成できる最大の1...の区間を求めればよいです。
0...1...0..のような区間を反転させても、結局そこを利用しつつ最適解にするには、初期の時点で1...であった部分をもう一度反転する必要があり、結局反転が必要な回数は変わりません(0...1...0...1...0...のように、入れ替わりの個数が増えても、結局は同じことです)。
ということで、1...0...の区間を連続で個とり、その区間、そしてその右にある1...の区間を合わせた長さを求め、この長さの最大値を求めていけば、答えになります。
これは、しゃくとり法のように、左端と右端をやり取りしていけば、で求めることができます。
実装時は、もし入力された文字列が0...1...0...のように、両端が0で終わるパターンでも、'1'が0個つながった区間が存在すると仮定すると、端の処理でバグることが少なくなります。
と先輩がツイートをしていました。
Dは端が0の時は、1が0個あると思うと楽
— 鍋食べたいbot (@__imulan__) 2019年4月13日
この処理をしたのが提出コード(2)になります。(1)はとくに何もしてないです。
この処理をすることによって、1...0...を問答無用で1つのセットとみなすことができます。
あとは、いつもの尺取り法のように、区間の両端を用意して、0...の区間の個数が
個になるように、
を増やして区間を広げたり、
を増やして区間を狭めたりして、答えとなる区間の長さを求めていけば良いです。
感想
尺取り法はいつも雰囲気で書いているので、forを使ったりwhileを使ったりとパターンがバラバラになっていて、少し実装に時間がかかっているイメージがあります。
統一すると、テンプレ化できてスピードがはやくなったりするのでしょうか。
解法は、まず、この問題っぽいなぁと思ったのですが、特に関係してなさそうなので、最善手をひたすら考えました。
