mini-notes

競技プログラミングの解法メモを残していきます。

ARC102 D - All Your Paths are Different Lengths (700)

問題:D - All Your Paths are Different Lengths

解答:Submission #10121089 - AtCoder Regular Contest 102

メモ:解説AC。。

多重辺が許容されているのが重要。Lが2べきの時は、例えば頂点①②③④のようなグラフに対し、①→②に長さ1の辺と0の辺、②→③に長さ2の辺と0の辺、③→④に長さ4の辺と0の辺を追加すると①→④について長さ0~7のパスができてOK。

Lが2べきでない場合、2べき以降の辺をどうやって作るかだが、例えば上記の例で①→④に長さ8の辺を追加すると長さ0~8のパスができる。②→④に長さ8の辺を追加すると長さ0~9のパスが追加できる。

つまり頂点iに長さXの辺を追加するとX, X+1, ... , X + 2i-1 - 1のパスが追加できる。よって追加すべきパスの個数に応じて各頂点で辺を追加するかを決めてゆけばよい。