- 回文
- 考えたこと
- 最初の文字列を選ぶ
- 最後に来ることができる文字列が限られる
- 総コストが小さい順に探索していって見つかったら終了
- 最初と最後を見た後は？
- どちらが短いかによる
- 短い側に追加する
- 長さが同じなら？
- それは回文成立
- 長さが違っていても回文成立することがある
- 例a, ba
- 「回文が成立しているかどうか」の低コストな判定が必要？
- 長い方を短い方の長さで切った時に残ってる部分が回文
- 罠の気配
- コスト10^9の回文と、コスト1の「いくら組み合わせでも回文にならないが回文の可能性が残り続ける部品」があった時に後者を10^9回試してしまう気がする
- そんなパターンがあるか？
- abc, a, cbcb, bcbcとかでどう？
- ダメ
- 思いつかないのでないと仮定して実装してTLE で怒られたら反省する流れか
- 公式解説
- 「回文でないところだけを保持」
- なるほど、既出パターンにたどり着いたら千日手だからその先を探索する必要はないわけか
- 可能な遷移をグラフにし、「空文字」もしくは「余りが回文」をゴールとする最短経路問題
- 状態遷移図の最短経路問題
- 「回文でないところだけを保持」
