読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Educational Codeforces Round 17: D. Maximum Path (Simpath)

Codeforces Simpath

非想定解法です。普通に解いた方が明らかに楽です。

http://codeforces.com/problemset/problem/762/D

解法

Simpath と呼ばれているアルゴリズムを用いて DP できる。Simpath が指してる意味が間違ってたらごめん。

Simpath というのは数え上げお姉さん問題でも登場するアルゴリズム。ZDD との関連で出てくるので名前だけ知っている人も多いかと思う。しかしその実態は動的計画法と何ら変わらない。

Simpath では dp[mate配列] := 最大経路コスト とする。mate 配列というのはパスの情報を表現する配列である。mate 配列の定義は以下が詳しい。

d.hatena.ne.jp

辺集合が 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 で通った。