GCJ 2016 Round 1C Problem B. Slides!

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

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

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

とすると、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] 以下の任意の整数を作ることができる。

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