ABC175F

https://gyazo.com/de4ce184d63017d1bb7b3f0b430e77cc

考えたこと

最初の文字列を選ぶ

最後に来ることができる文字列が限られる

総コストが小さい順に探索していって見つかったら終了

最初と最後を見た後は？

どちらが短いかによる

短い側に追加する

長さが同じなら？

それは回文成立

長さが違っていても回文成立することがある

例a, ba

「回文が成立しているかどうか」の低コストな判定が必要？

長い方を短い方の長さで切った時に残ってる部分が回文

罠の気配

コスト10^9の回文と、コスト1の「いくら組み合わせでも回文にならないが回文の可能性が残り続ける部品」があった時に後者を10^9回試してしまう気がする

そんなパターンがあるか？

abc, a, cbcb, bcbcとかでどう？

ダメ

思いつかないのでないと仮定して実装してTLE で怒られたら反省する流れか

公式解説

「回文でないところだけを保持」

なるほど、既出パターンにたどり着いたら千日手だからその先を探索する必要はないわけか