Eまで五完。
コンテスト後のツイート
E 正六角形に充填していくのが最良。(0,0)から置いて行ったら通らず、ちょっとずらして、不要なものを消したらいけた。（WAは出力がnより大きいせいかも）
— titia (@titia_til) April 21, 2026
F k番目の辞書式最小化をしようとしていた。これはsuffix-arrayで二分探索するとできそう。サンプルが合わず、終了30秒前に最大化だと気付いた。
F. String Cutting
解説AC。
コンテスト中に考えていた方法はダメだった。誤読で間違えただけだったら、ちょっと直せば通るはずだけどそれでは無理で、根本的に間違っていた。
気付いていなかったのは、
・各開始位置indexについて、S[index:?]を考えるとき、n,k,lの条件から?は定まる。（そもそもその開始位置では条件を満たさないものもあるが、それも判定できる）
ということ。
言われてみれば当たり前ですね。
これを使えば、Suffix-arrayとLCP配列を使ってどの開始位置が最適かを調べることができる。
Suffix-array配列をSAとすると、SAの中でできるだけ後ろにある開始位置が良い。その長さがLCP配列より大きければそれが答え。そうでなければ、SAの一つ前の開始位置のものの方が良いかもしれないので比較していけば良い。
0 件のコメント:
コメントを投稿