第12回 JOI 本選 : Tower of JOIOI

問題

長さ N の 'J' 'O' 'I'の文字しか含まれない文字列 S が与えられる．

i < j < k において

を満たす (i, j, k) の数の最大を求める．ただし，一度使った i, j, k は使うことができない．

制約から O(nlogn) か？となる．

サンプルを試しながら性質を分析する．

最初はdpっぽく解けるのかなぁと思ったけど部分問題に落とし込むことができなくなってこれは違うなと思った．

サンプルを試すと JO の次の Iに関して注意して考えると良さそうな気がしてくる．いろんな例で試してもあまり自明に思えないので，これは間違いっぽいということが分かる．

今は前から見ることばかり考えてたけど，後ろから I と O を決定すると，それより前のJを貪欲に使っていけそうなことが分かる．

ここまで考えて行き詰ったので解説を見る．

なるほど二分探索で右側のIの数を固定するのか，となって終了した．

考察は良さそうなところまでいってる気はするけど，最後の詰めが出来ない．最初の制約から計算量を推測するところで二分探索の可能性を頭の中に残しておくべきだった．

あと実装力が全然足りてないので，変な実装をして O(N²) になってたのも残念すぎる．

問題文からはそう見えないけど解答がクエリっぽいなと思った（今見ている添字の前の状態しか見る必要が無いので）．