hotpepsiの練習帳

SRM 527 Div1

20:28

Easy (275) P8XGraphBuilder

問題

• N個のノード(node)をN-1本の辺(edge)でつないだグラフを作る。
• グラフは連結グラフである。すなわち、任意の2つのノードは辺により接続されている。
• あるノードから別のノードで出ている辺の本数を次数(degree)とする。
• 次数毎のスコアの配列が与えられる。
• グラフのスコアは、各ノードの次数に応じたスコアの和である。
• 最大スコアを求めよ。
• なお次数のスコア表のサイズ+1がノード総数である。

方針

• 連結グラフでN-1本しか使えないので、木になる(閉路はない)
• 構成可能な木の組み合わせのうち、最大スコアを求める問題
• ある個数Xのノードを使った全ての木の組み合わせが試せればよい
• 本番では木の下に複数の木がある組み合わせができなくて爆死
• kinabaさんのを見て、葉+木のパターンだけ試せばよい理由がわからなかったので図を描いた
  
• 図のAとDを交換しても、次数の組み合わせは変化しない
• 図でいうと右下の部分は必ず葉
• 「部分木が最も右側以外にある場合、右下の葉と交換」という操作を繰り返すと、任意の木が、根+(葉+木(葉+木(葉+木...)))という形に変形できる
• やっとできた...
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_527/P8XGraphBuilder.cpp

Div2 Hard (950)

問題

• 貨幣価値が2の累乗になっているN種類の硬貨がある。
• ちょうどcoins_count枚の硬貨で、合計をcoins_sumをにしたい。
• 辞書順最小の組み合わせを求める。

方針

• この問題での辞書順最小の定義は、最も貨幣価値の低い貨幣を最小にすることである
• 最低価値の貨幣だけの状態からスタートして、coins_countを超えている場合には、貪欲にひとつ上の貨幣に交換していく
• 最後の交換の結果、coins_countと一致していなければ失敗
• 証明はAnalysisを読んだ
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_527/P8XCoinChangeAnother.cpp

結果

x-- 0.0pt 511st rating 1243 -> 1231

とりあえずeasyだけ通すのが目標だったのだが2回目でdiv1の壁に当たった。

ストーリーなしでいきなりグラフかよ!とちょっとだけ思った。まあ今回はストーリーつけづらい感じではあった。