notepad.exe

つまり覚え書き

ABC108/ARC102 D - All Your Paths are Different Lengths

AtCoder アルゴリズム D問題

復習日記

700点問題はさすがに難しいので解説その他もろもろを見ながら解きました

問題ページ

問題概要

整数 $L$ が与えられるので以下の条件を満たすグラフを一つ出力。

頂点が $N$ 以下で頂点の番号は $1 ～ N$ まで
辺数 $M$ が60以下で長さが $0 \leq M \leq 10^{6}$
辺は頂点の数字が小さいほうから大きいほうに引く
頂点1から頂点 $N$ までのパスがちょうど $L$ 個あり、各パスの長さが $1 ～ L - 1$ まで

考え方

一つ目のサンプルが少しヒントになっていると感じました。ポイントは長さ1でつながってるパスがあり、そのパスに対して長さ0の辺を引いているところ。長さの順にパスを並べてみると、

[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 1, 1]
[0, 1, 1, 1]

というようになっていて、ここから2進数のように見える発想が出れば解法の半分までたどり着くことがで来そうです。
$N$ 個の頂点に対して辺の長さを1だけでなくて $1, 2, 4, ... , 2^{N-1}$ と変えて同じように0の辺を作れば $1 ～ 2^{N-1}$ のパスを作ることができます。 f:id:mosmos_21:20180903173143p:plain

これで $2^{N}$ ちょうどの時なら作ることができました。ここで例えば $L = 12$ だとすると上の図では $8 ～ 11$ のパスが足りません。
この時に、下の図のように1本辺を足すと $N$ までのパスが4通り増えて必要なパスをすべてそろえることができます。 f:id:mosmos_21:20180903195818p:plain

パスの数を足すには例えば6本足したいときには2本と4本( $2^{k}本$ )に分けてパスを追加することで過不足なくパスを増やすことができます。

最後に制約の確認をすると、

頂点は20個までなので、 $2^{20} - 1 = 1048575$ なので $L = 10^{6} \lt 2^{20} - 1$
辺は20個の頂点の時に、 $19 * 2 + 19 = 57 \lt 60$

となるので問題なさそうです。

提出コード

やはり700点問題は難しいですね。