ARC102 D問題 All Your Paths are Different Lengths

なんか最近難化傾向にあるような...
D - All Your Paths are Different Lengths

<考察>
1. 以下のようにノード 間に長さ の二つの辺を貼ると ,
　 の時のグラフが表現できる.

2. をサイズが2の累乗の区間の和で表すことを考える.
　　( ルール : サイズの大きい区間から貪欲に決めていくこと )

　　例1 :
　　　
　　例2 :
　　　

　　これと同じようにグラフをそれぞれ作ると ...

こうすると , 同じ長さのパスを一つも作ることなく , グラフを構築することができました .
pythonでの実装

L = int(input())
# ノード数を決める
for i in range(1,21):
    if (1 << i) > L:
        node = i
        break

# 必ず 0と2^Nの辺を貼る
edge = []
for i in range(node-1):
    edge.append((i+1,i+2,0))
    edge.append((i+1,i+2,1<<i))

# 2の累乗の区間に分割
for i in range(node-1):
    if (L >> i) & 1:
        edge.append((i+1,node,L-(1<<i)))
        L = L-(1<<i)

#出力
print(str(dig) + " " + str(len(edge)))
s = "{0} {1} {2}"
for v,v2,w in edge:
    print(s.format(v,v2,w))