hotpepsiの練習帳

SRM 703

22:04

https://competitiveprogramming.info/topcoder/srm/round/16848/div/1

Div1 Easy (250) DAGConstruction

問題

• N個の頂点と、それぞれの頂点が持つ値xが与えられる
• 以下の条件を満たす有向グラフを構築せよ
  • 閉路は存在しない
  • 任意の2頂点間の辺は高々1つ
  • 頂点iから到達可能な頂点の数はx[i]個

方針

• 葉は1
• x[i]==2は、葉につなげばよい
• x[i]==3だったら、2のものにつなぐか、2つの葉につなぐ
• 4だったら、それまでに出現した3つの頂点につなぐ
• x[i]が小さい頂点から処理していき、それまでに出現した頂点につなぐだけでよさそう
• それまでに出現した全ての頂点につないでも数が足りないときは不可能
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_703/DAGConstruction.cpp

結果

o-- 120.72pt 122nd/209 rating 1348 -> 1370 (+22)

大きな頂点につないだ結果、オーバーするかどうかの判定を入れて再提出したのだが、不要だった。

最初に出現したものからひとつずつつないでいくが、子の頂点を持つ頂点を追加する場合も、それらの子の頂点はすでに追加済で、ひとつずつしか増えないので、オーバーしない。

https://togetter.com/li/1059299