ABC135 F Strings of Eternity

やる

問題文

読んで

考察

自明に単調性があるので、二分探索で決め打てそうなことがわかります。問題は決め打ったときの判定なので、まずはそこを考察していきます。

ひとまず愚直に考えます。を回連結した文字列を作ります。ではを回連結した文字列はの部分文字列を持ちますか？という問題がめっちゃ速く解けると嬉しいですね。

厄介なのはを回連結するというところです。の方は二分探索で決め打つので良いのですが、はそう上手くいきません。何か上手く考えると一意に定まりそうな気配もしますが、愚直に時間をかけてもアレなんですよね...。ひとまず置いておきます。

二分探索で判定は、愚直にやると筋が悪い気がしてきたので別方面を考えます。

何も思いつかないので解説を見ました。あ～～～～文字の関係をグラフとして解釈するやつ三回は解いたのに忘れてたなあ.....。 はの大体二倍くらいの長さにしてあげれば良くて、あとはロリハなり何なりで辺張って、ループがなければUFして連結成分の最大値取っておしまい。

ループがあったらにして、そもそも辺が張られていなければ。

うわ～かしこい。言われれば素直に出来るし、解けるべきだったなあと......