SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458）

　Eまで。またレート1800を割る。

コンテストへのリンク

コンテスト後のツイート

SMBCプログラミングコンテスト #1（AtCoder Beginner Contest 458） Eまで。Fの12WAが取れない。何故！？
C Cの文字からmin(最初への距離,最後への距離)
D SortedMultiset
E 1313……が何回続くかで考える。
F Trie木のnodeを使って行列累乗。Aho-Corasick法で遷移行列を見つける。で良いと思ったがWA

— titia (@titia_til) May 16, 2026

F - Critical Misread

　コンテスト中の方針で大まかなものはあっていたが、どこでWAになるか分からず、ランダムテストでACしている提出と比較した。

　ミスは次のようなものだった。

　たとえば、"bcb"と"c"がある場合に、"bcb"が出たらそもそもいけないのだが、"bc"や"bcb"もノードとして数えてしまっていた。

　そのようなものを削る前処理を行ったらAC。

　Aho-Corasick法を使う場合に、必要になることが多い前処理という気がするが、知らなかった。

　そして、AIに聞いたところ、Failure_pathを利用して"c"に印がついているなら、"bc"にも印がつくようにする、という構築を行うのが一般的らしい。勉強になった。