Loading...
2/26/2025
頂点の有向グラフがあり、頂点からの向きに文字のラベルが付いた辺がある。ただし、が-
のときは辺がない。全てのの組に対して、以下の問いに答えよ。
頂点から頂点へのパスであって、ラベルを通った順に読んだときにそれが回文となるようなパスのうち、最も短い長さがなにかを求めよ。
重要な考察として、回文の先頭と末尾に同じ文字を加えた文字列はまた回文となる、というものがある1。また、空文字列と文字1文字からなる文字列は回文である。
これを用いて、「すでに構築済みの回文の最短経路から左右に1文字ずつ同じ文字を伸ばすことによって回文を生成していく」ということを考えたい。これは、頂点から頂点へのパスが最短となる回文の長さ(これをとする)が既知であるとして、(が未知であるような)頂点の組で「頂点から頂点へ向かう辺のラベル」と「頂点から頂点へ向かう辺のラベル」が同じ場合はと表すことができる。これは、先に述べた「回文の先頭と末尾に同じ文字を加えた文字列はまた回文である」を用いている。
以上を用いると、問題は以下のように言い換えることができる。
頂点からなるグラフと表が与えられる。頂点と頂点の間には2、であるとき、またその場合に限り重み2の有向辺が貼られている。 ここで、頂点の距離は0で、またが
-
ではないような頂点への距離は1である。全ての頂点への最短距離を求めよ。
一般的な最短経路問題に帰着されたので、Dijkstra法か、あるいはキューに追加する順に注意をしてBFSをすることにより求めることができる。