2026年4月16日木曜日

AtCoder Beginner Contest 452

 Fまで解けたが遅かった。

コンテスト後のツイート


G - 221 Substring

 自力AC。

 コンテスト中の方針であっていた。数字の個数=数字の大きさならそのまま、個数が数字の大きさより大きければ、k 0 kと置き換えて並べる。
 その上で、Suffix array、各indexから0までの個数を調べていく。そのままだと重複が出るが、LCP配列を使えば重複は除ける。

 コンテスト中に失敗していたのは、自分のライブラリだと文字列Sの後ろに、最も小さい文字(今回は数字)を置いておかねばいけないところだった。あとは、SA[i]でi番目に小さいindexを表すのだが、その逆関数なのかどちらか分からなくなって混乱したところ。ただ、これは久しぶりにSuffix arrayを使ったのだからしょうがない気もする。

 後はすんなりできた。
 Fより時間かからなかったと思うので、F捨ててG行けば通せてたかなぁ。


0 件のコメント:

コメントを投稿