Educational Codeforces Round 17: D. Maximum Path (Simpath)
非想定解法です。普通に解いた方が明らかに楽です。
http://codeforces.com/problemset/problem/762/D
解法
Simpath と呼ばれているアルゴリズムを用いて DP できる。Simpath が指してる意味が間違ってたらごめん。
Simpath というのは数え上げお姉さん問題でも登場するアルゴリズム。ZDD との関連で出てくるので名前だけ知っている人も多いかと思う。しかしその実態は動的計画法と何ら変わらない。
Simpath では dp[mate配列] := 最大経路コスト とする。mate 配列というのはパスの情報を表現する配列である。mate 配列の定義は以下が詳しい。
辺集合が s-t パスであるための必要十分条件は以下の通り。
- s, t の次数が 1
- s, t が連結
- s, t 以外の頂点の次数は 0 または 2
- 閉路が存在しない
mate 配列により上の条件は以下のように言い換えられる。
- mate[s]=t
- mate[t]=s
- u≠s, u≠t, mate[u]=-1 または mate[u]=u
まず(0,0) から幅優先探索を行い、辺に順番をつける。dp[i番目の辺まで考慮した][mate配列] := 最大経路コスト というDPができる。しかし、mate 配列は頂点数と同じだけのサイズ必要になるため、計算量が抑えられない。
ここでフロンティアという考え方がでてくる。i 番目以降の辺を使っても mate[u] が変わることがないのであれば、mate[u] の情報を捨ててしまっても良い。また、1..i の辺から離れた頂点は mate[u]=u なので、これも捨ててしまって良い。こうすると、最終的に必要になるのはフロンティアと呼ばれる頂点のみになる。
今回の問題では、フロンティアとなる頂点数が極めて少ない（3頂点）ため計算量が大幅に抑えられる。
動的メモリ確保をしてしまうと実行時間が遅くなるため注意。654 ms で通った。
