pekempeyのブログ

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

GCJ 2016 Round 1C Problem B. Slides!

https://code.google.com/codejam/contest/4314486/dashboard#s=p1&a=2

問題

頂点 0 から頂点 B-1 への経路数が丁度 M になるような頂点数 B の有向グラフを構築せよ。

  • 2≦B≦50
  • 1≦M≦1018

解法

グラフに閉路があると経路数が無限大に発散する可能性があるので、DAG に限定する。

できるだけ辺を繋いでグラフを構成する。たとえば E={(i,j): i<j}={(0,1),(0,2),(0,3),...,(0,B-1),(1,2),(1,3),...} とする。

  • dp[i] := 頂点 i への経路数

とすると、dp=[1,1,2,4,8,16,32,64,...] になる。dp[B-1] より大きくできないので M>dp[B-1] であれば構成不可能である。一方 M≦dp[B-1] なら構成可能である。

dp[B-1] の式に着目する。

$$ dp[B-1]=dp[0]+dp[1]+dp[2]+...+dp[B-2] $$

であるが、辺 (i,B-1) を除去することにより dp[B-1] -= dp[i] ができる。dp テーブルに入ってる値は 2 の冪なので二進法の要領で dp[B-1] 以下の任意の整数を作ることができる。

GCJ 2016 Round 1C Problem B. Slides!

とりあえず最大ケースを作ってみると気付く。