先週の土曜日に開催されたABC408は、開始時間までに帰ってくることができなかったため、次の日にバーチャル参加を行いました。
結果は、ABCの3完でした。A、B問題でそれぞれ1回、3回のWAを出してしまい、バタバタしましたが、C問題は割とすんなり解けたので、D問題に時間をかけることができました。一度は提出したものの、結果はWAとなってしまいました。
01の文字列に対して、0→1や1→0の反転を行って、1の塊が高々1つにする問題だったと思うのですが、私は「0→1の操作のみ」または「1→0の操作のみ」で条件を満たす方法ばかりを考えており、それでは対応できない（どちらの操作も必要となる）ケースがあるようでした。
ただ、どのような場合がコーナーケースになるのかは、まだはっきりとはわかっていません。
とりあえず、処理時間を無視して、1の開始位置（l）と終了位置(r)を全探索する方法を試したところ、TLEは出るものの、WAとなっていたテストケースは問題なく通っていました。
公式解説などでは、この全探索を高速化するために、累積和を使った解法やDPを用いた解法が紹介されていて、まだまだこうした解法を時間内に思いつけるレベルには達していないなと痛感しました。
実際、AtCoder Problemsで確認すると、D問題は緑diffだったようで、なるほどと納得しました。
本日、また頑張ります。