7K12 blog

猫でも分かるアルゴリズム解説

Educational DP Contest: G Longest Path

f:id:tkr987:20200211004925p:plain

https://atcoder.jp/contests/dp/submissions/10552064

この問題は動的計画法の勉強というより幅優先探索の勉強という感じ。BFSが実装できればDP部分で苦労することはないと思う。

 

最短経路でなく辺の長さ最大を求めなければならないので、入次数を管理する配列degを用意して処理する。具体的には「BFSで頂点を辿りながら頂点xに接続している次の頂点yをチェックする瞬間にdeg[y]をデクリメント」する。deg[y]がゼロでなければ何もせず、deg[y]がゼロになった瞬間にDPを更新すれば問題が解ける。BFSのスタート地点は入次数が最初からゼロの頂点とする。

 

BFSについて「Nステップ目の処理でNステップで到達できる辺を全探索する」という大事な性質は暗記すると効率が良いかもしれない。deg[y]をデクリメントしていく行為は頂点xから頂点yへの辺を壊す行為に等しい。BFSの性質からN回目のループでNステップでスタート地点から到達できる辺が全て破壊され、次のループでN+1ステップでスタート地点から到達できる辺が全て破壊される。つまり入次数がゼロになった瞬間が最大経路ということになる。基本的にBFSは各頂点を1回だけキューに入れて処理する仕組みになるので、入次数が0になったタイミングで頂点をキューに入れることで最適解が得られる(たぶん)。

f:id:tkr987:20200211011513p:plain

ただし、注意点として入次数ゼロの頂点が最初から複数あったときは全てキューに入れてからBFSを実行する必要がある。例えば、画像のようなグラフで最初に赤から青への頂点をBFSしてしまうと緑から青への辺しか残らず最長が求まらない (赤から青へのBFSだけ最初に実行してしまうと入次数がゼロでないので何も起こらない)。

また、出次数の変数も用意しておくと頂点インデックスが存在しないから入次数ゼロなのか入次数がゼロの頂点なのか、判別しやすかったりして色々と実装するときに役立つことが多い。