AtCoder Beginner Contest 272

　Fが解けず。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 272 Fが分からなかった。
A sum
B 人iが参加した舞踏会一覧を持って全探索。
C 偶奇で分ける
D BFS
E 各数が0～500になるのはいつかを調べる。答えが500以上になるなら、愚直に計算。
G Mの候補はある二数の差の約数なので、乱択する。

— titia (@titia_til) October 8, 2022

F - Two Strings

　解説AC。

　コンテスト中、Suffix arrayを見てこれを使うのでは？　と思い、S、TをSuffix arrayを作るようにソートすれば、尺取りで解けそうと考えた。が、同じ文字が続く場合や、SとT（を回転させたもの）が一致するときの処理が上手くできなかった。

　Suffix arrayをもっと上手く使えないか？　と考えるべきだった。

　SやTを回転させたもの全てを調べたいので、S+S、T+TにSuffix arrayを使う。

　さらに、SとTを直接比較したいので、S+S+T+TにSuffix arrayを使う。

　そして、同じ文字が続くときの処理のため、S+S+"a"*N+T+T+"z"*NにSuffix arrayを使うと答えが得られる。