7K12 blog

猫でも分かるアルゴリズム解説

ABC108 D - All Your Paths are Different Lengths

f:id:tkr987:20200411004104p:plain

https://atcoder.jp/contests/abc108/submissions/9690709

dif1800なので数学的考察力が必要、難しい。


各頂点をビットと考えると2進数で表現できそうという気持ちになる。頂点[0]から頂点[19]まであるので 2^{19}=5*10^{5}で若干足りないが、とりあえず L= 2^{k}なら各頂点を0と 2^{i}の両方の辺で繋げていくことにする。これで半開区間[0, 2^{19})までの L= 2^{k}だけ表現できる。

f:id:tkr987:20200411015146p:plain
 2^{19}-1を超える値や L=2^{k}+pのときが難しい。とりあえず辺の数が余っているので、更に辺を追加することで表現できる値を増やしたい。具体的にはLを2進数にしてL[k]=1になってる頂点から末尾の頂点へ辺E[k]を更に追加することで対応する。例えばL=22=10110のとき追加するE[i]の長さは初期値が E(i)=2^{4}で追加する毎に E(i+1) = E(i)+2^{i-1}と長くしていく。これで中途半端な値も表現できる上に [0, 2^{20})まで表現できる。

 

参考: https://betrue12.hateblo.jp/entry/2018/09/02/094954