ARC102 D問題 All Your Paths are Different Lengths

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

<考察>
1. 以下のようにノード  n , m 間に長さ  0 , 2^{n} の二つの辺を貼ると ,
  L = 2 ^ {node} の時のグラフが表現できる.

f:id:banboooo:20180902143647j:plain:w300

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

  例1 :
    [0 , 10) =  [0 , 8) \  \bigcup \ [8 , 10) \\ 
   = [0 , 8 )\  \bigcup \  [ 8 + 0 , 8 + 2 )
  例2 :
    [0 . 15) =  [0 , 8)\  \bigcup \  [8 , 12) \  \bigcup \ [12 , 14) \ \bigcup \ [14 , 15) \\ 
                                = [0 , 8) \ \bigcup \ [ 8 + 0 , 8 + 4 ) \ \bigcup \ [ 12 + 0 , 12 + 2 ) \ \bigcup \ [ 14 + 0 , 14 + 1 )

  これと同じようにグラフをそれぞれ作ると ...
f:id:banboooo:20180902152739j:plain:w500

こうすると , 同じ長さのパスを一つも作ることなく , グラフを構築することができました .
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))