問題

問題リンク

$N$頂点の有向グラフがあり、頂点$i$から$j$の向きに文字$C_{i, j}$のラベルが付いた辺がある。ただし、$C_{i, j}$が-のときは辺がない。全ての$(i, j)$の組に対して、以下の問いに答えよ。

頂点$i$から頂点$j$へのパスであって、ラベルを通った順に読んだときにそれが回文となるようなパスのうち、最も短い長さがなにかを求めよ。

考察

重要な考察として、回文の先頭と末尾に同じ文字を加えた文字列はまた回文となる、というものがある¹。また、空文字列と文字1文字からなる文字列は回文である。

これを用いて、「すでに構築済みの回文の最短経路から左右に1文字ずつ同じ文字を伸ばすことによって回文を生成していく」ということを考えたい。これは、頂点$i$から頂点$j$へのパスが最短となる回文の長さ(これを$D_{i, j}$とする)が既知であるとして、($D_{x, y}$が未知であるような)頂点の組$x, y$で「頂点$x$から頂点$i$へ向かう辺のラベル」と「頂点$y$から頂点$j$へ向かう辺のラベル」が同じ場合は$D_{x, y} = D_{i, j}+2$と表すことができる。これは、先に述べた「回文の先頭と末尾に同じ文字を加えた文字列はまた回文である」を用いている。

以上を用いると、問題は以下のように言い換えることができる。

$N^2$頂点からなるグラフと表$C$が与えられる。頂点$(i, j)$と頂点$(x, y)$の間には²、$C_{x, i} = C_{j, y}$であるとき、またその場合に限り重み2の有向辺が貼られている。 ここで、頂点$(i, i)$の距離は0で、また$C_{i, j}$が-ではないような頂点$(i, j)$への距離は1である。全ての頂点への最短距離を求めよ。

解法

一般的な最短経路問題に帰着されたので、Dijkstra法か、あるいはキューに追加する順に注意をしてBFSをすることにより求めることができる。

提出

Footnotes

1. 言われれば当然と言えば当然 ↩

2. 2つ組で1頂点であることに注意 ↩