https://atcoder.jp/contests/abc108/submissions/9690709
dif1800なので数学的考察力が必要、難しい。
各頂点をビットと考えると2進数で表現できそうという気持ちになる。頂点[0]から頂点[19]まであるのでで若干足りないが、とりあえず
なら各頂点を0と
の両方の辺で繋げていくことにする。これで半開区間
までの
だけ表現できる。
を超える値や
のときが難しい。とりあえず辺の数が余っているので、更に辺を追加することで表現できる値を増やしたい。具体的にはLを2進数にしてL[k]=1になってる頂点から末尾の頂点へ辺E[k]を更に追加することで対応する。例えばL=22=10110のとき追加するE[i]の長さは初期値が
で追加する毎に
と長くしていく。これで中途半端な値も表現できる上に
まで表現できる。
