任意の文字列は全て同じ文字からなる。文字、...と区切ってできた部分文字列は全て回文である。文字、...と区切ってできた部分文字列は全て回文である。解説まず、回文という条件は「対称の位置にある文字を同じにする一種の縛り」と見ることができる。そこで「文字を頂点として同じ文字同士に辺が張られたグラフ」というのを考えると、「全ての文字が同じ」というのは「グラフが連結である」ことと同値になる。これでUnion-Findなり使えばジャッジはできるようになったが、今回は構築の方なのでもっと深く考える必要がある。すれば上手いこと連結になる。いうのも、右端の余った1頂点を使って隣に繋げればいい。以下に隣の回文領域の頂点数が偶数の場合と奇数の場合を示す。見ての通り、偶数の場合は上手くいくのだが奇数の場合は上手くいかない。実は両端以外に奇数頂点の回文領域がある場合は全体を連結にできない。いうのも、全体を連結にするには辺の数が足りないのだ。いうわけで、奇数の要素数が3以上ならImpossibleを返し、そうでなければ奇数要素を両端に移動させて上の構築方法を実行すればいい。0;}上では複雑な話をしたが、要はaの先頭を1減らして末尾を1増やすだけで構築できてしまう。実装自体は非常に軽い。類題の話この問題と傾向が似てる問題として、ARC048-C「足の多い高橋君」が挙げられる。アブノーマルな問題設定で有名な問題だが、この問題同様「どれが同じ文字になるか」を考えるのが鍵となる(多分)。運良く方針が正解へ向いていた。回文をグラフと見るのは結構重要な発想かもしれない。今夜のAGCもこれくらい調子が良いといいなぁ。