freee プログラミングコンテスト2022(AtCoder Beginner Contest 264) G - String Fair (600)
コンテスト中の考察
最後の二文字によって状態を判別できる
1文字の場合は他のと組み合わせて2文字以上のTを作る
一度遷移を作製した後もう一巡して値が更新されていたら無限に値が大きくできる
そうでなければ現在の値が答え
Tにある文字列からしかSを構築できないと思っていた
解説の解法
初期状態を$$としておく
0文字、1文字、2文字の状態全てを点として持って遷移可能なところに辺を張る
一文字追加したときの変化は、その一文字の美しさ、最後の一文字とその一文字の美しさ、最後の二文字とその一文字の美しさの合計
これが無限に大きくなるかどうかは美しさを反転してベルマンフォード法で解ける