phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

ARC102 D. All Your Paths are Different Lengths

問題

整数Lが与えられるので、以下の条件を満たす有向グラフを返せ。

  • 多重辺が含まれていてよい
  • 頂点数Nは20以下で、すべての頂点は相違な1~Nの番号が付けられている
  • 辺数Mは60以下で、すべての辺には0~10^6以下の整数の長さがつけられている
  • 辺は、頂点番号が小さいものから大きいものへとのみ張られている
  • 頂点1から頂点Nへの異なるパスがちょうどL個、かつ、それらパスの長さが0~L-1までの相違な整数になっている
    • パスの長さとは、パス上の辺の長さの総和
    • 異なるパスとは、パス上の辺の集合が異なること

制約

  • 2 <= L <= 10^6

解法

まず、「パスの数がちょうどL個」の方から考える。
頂点数が20程度で10^6個のパスを作る必要があり、2乗をうまく駆使してグラフを作る必要がある。
多重辺が許されない場合は、すべての頂点から辺が張れる頂点へ辺を伸ばすと各頂点へのパスが2乗になってくれるが、辺の数が60本を超えてしまう。
多重辺を許される場合、頂点間の辺の本数を1本から2本にすると、そこまでのパスを2倍にすることができる。
したがって、単純にN頂点を番号順に並べて、頂点iから頂点i+1へ辺を2本張れば、各頂点へのパス数が2乗になって、Lを2進数で表記したとき1となるものに対応する頂点から最後の頂点へ辺を張ればパスの数をちょうどL個にできる。


ただし、Nの制約が20以下で、頂点数がかなりぎりぎりのため、2乗の頂点とは別に最後の頂点を用意しようとすると足りなくなってしまうので注意。
イメージとしては以下のような感じ(頂点1~4まででパスを作って、2進表現に該当する部分を長さW,X,Y,Zの辺の有無で調整)だけど、
f:id:phyllo_algo:20180902133910p:plain
頂点数を節約するのに以下のようにして頂点を減らして考えた。。。
(長さWの辺は自己ループになるので削除し、代わりに一つ前の頂点から伸びている辺(長さ0と長さ4の辺)の長さにWを加算して扱う)
f:id:phyllo_algo:20180902134005p:plain


次に「パスの長さが0~L-1までの相違な整数になる」を考える。
今、辺は「隣り合う頂点に2本」と「各頂点から最後の頂点へ1本あるかないか」の状態になっている。
パスがL個で0~L-1までちょうど使い切る必要があるため、きれいに割り当てないといけない。


ここで、規則性を持たせるため、隣り合う頂点間の2本の辺に「長さ0の辺」と「長さ2^(i-1)の辺」を貼ることを考える。
すると、各頂点までのパスの長さは「0~(2^(i-1))-1の長さがすべて含まれる」。
あとは、「各頂点から最後の頂点への辺(図でいうところのW, X, Y, Z)」の部分で、0~L-1に被らないように割当たるように辺の長さ(W, X, Y, Z)を決めてあげればぴったり割り当てられる。
(後ろから決めていく方法だと、Lからパスの数を引きつつW, X, Y, Zの順番で値を決めていく。Zは必ず0)

解法2

解説放送での方法。
AtCoder Regular Contest 102/ Beginner Contest 108 解説放送 - YouTube
L=Xがわかっているとき、「L=2Xを作る方法」と「L=X+1を作る方法」が決まれば、それを繰り返すことで構成することができる。


最小のL=2の時は、頂点数が2つで、頂点1から頂点2への長さが0の辺と1の辺であることが一意に決まる。


「L=2Xを作る方法」は、新しく頂点を追加し、L=Xでのグラフの最後の頂点から新しく追加した頂点へ辺を2本追加してあげればパスの数を2倍にできる。また、L=Xでのグラフの長さをすべて2倍にし、追加した辺の長さは0と1とすると作れる。
(追加した2本の辺の長さは0とXとするでもよい?)


「L=X+1を作る方法」は、一番最初の頂点から最後の頂点に辺を増やせばパスの数は作れる。辺の長さはXとすればよい。

反省

多重辺なしの2乗のイメージからスタートしてしまって、多重辺をうまく使えず、「パスの数がちょうどL個」の構成でハマってしまった。
基本的に、制約はすべて使い切って考える。