Shiritori(しりとり) - joi2011-day2 解説

筆者: qnighy

辺に番号があるとき、辞書順最小の有向オイラー路を求める問題である。

部分点解法

省略

(Kは頂点数)

有向オイラー路の存在判定は、無向基礎グラフが連結でありかつ、全ての頂点で入次数と出次数が等しいかまたはs,tが存在してsでは出次数のほうが1多くtでは入次数のほうが1多いことである。これについては詳しくは示さない。

もし全ての頂点で入次数と出次数が等しいならば、s=tかつ、どの頂点から始めてもよいことになるので、sを番号最小の辺の出る元に設定する。

さて、ここで図を参照されたい。

しりとりグラフの具体例。頂点は文字であり、辺は単語である。緑は出発点となる文字で、赤は目的地である。

ここで求められているのは辞書順最小の経路なので、使って良い辺のうち最も小さい辺を取るという貪欲法のような戦略を使えばよい。(その辺を取ることで、今いる頂点が移動し、同様の操作がN回繰り返される。)しかし、今いる頂点から出ている全ての辺を使っていいわけではないことに注意しなければならない。

強連結成分(互いに到達できるもの同士をまとめたグループ)を考えてみよう。上のグラフでは強連結成分は4つできる。

ところで、このグラフはオイラー路を持つので、強連結成分同士は必ず一列に連なっている。そして、今いる頂点はその最上流であり、目的地はその最下流に必ずある。

もし、最上流の強連結成分(紫で囲った部分)に、まだ通っていない辺(黒い辺)が残っているならば、強連結成分を「下る」辺(赤い辺)を通ってはいけないことになる。

逆に、黒い辺を辿る場合は必ずオイラー路を作ることができるので、黒い辺の中で最も番号の小さい辺を選べば良い。

ここで、辺を辿って良いかどうかの条件は次のように言い換えることができる。

その辺が黒い辺であるかどうかは、グラフの形状が変わるごとに、今いる点から逆向きに探索して到達できる範囲内かどうかを調べることでわかる。

重複辺がある場合、そのうち一方の辺を取り除いてもグラフの形状が変わらないことに注意すること。そのため、この検査のコストも実行回数もO(K^2)に抑えることができる。

よって全体の計算量はO(K^4+KN)となり、時間内に収まり満点が取れる。