Hatena::Grouptopcoder

hotpepsiの練習帳

2011-12-23

SRM 527 Div1

20:28

Easy (275) P8XGraphBuilder

問題

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

方針

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

Div2 Hard (950)

問題

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

方針

結果

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

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

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

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20111223