DPや全探索全てに通じる考え方
少し躓いた問題があったのでまとめる。
文字付きの有向グラフが与えられるので頂点 $i$ から $j$ へ向かうパスであり、辺についた文字を連結させた文字列が回文となるようなパスのうち最小の長さを全ての $i$ $j$ について求めろ。空の文字列は回文とみなす。
https://atcoder.jp/contests/abc394/tasks/abc394_e
頂点数 $N \le 100$
真っ先に思いつきそうな解法として全ての頂点から DFS をしてそれぞれの最短の回文パスを求める方法である。計算量が爆発する。
一旦わかることとして $i$ から $i$ に向かう場合は通るパスの文字を連結させたものは空の文字列になるので必然的に $0$ となる。
そして長さ $1$ の文字列は回文であるので $i$ から $j$ にパスが繋がっているならば答えは $1$ となる。 $( i \neq j)$
自明解を一旦書き出してみると自明解から新しい解(=最短回文パス)を作れそうな気がする。簡単に作れる回文パスから新しく両端に同じ文字を足せばそれは新しい最短回文パスになる。これは BFS によって実装できそう。
このように自明解がわかりきっている場合はそこから BFS や DP の考え方に持ち込むことができる。
$(i,j)$ という状態から、 $k$ から $i$ へ伸びるパスと $j$ から $l$ へ伸びるパスを両端に繋げれば新しいパスを作ることができる。(回文の定義より、このとき $k$ から $i$ へ伸びるパスの文字と $j$ から $l$ へ伸びるパスは一致していなければいけない。) ここで両端にパスを足すとパスの長さは $2$ 伸びるので $(k,l)$ の解は $(i,j) + 2$ となる。
必要な状態と遷移がわかったのであとはBFSを実装するだけ。