Hatena::Grouptopcoder

hotpepsiの練習帳

2014-08-13

SRM 629

02:05

Div1 Easy (250) RectangleCovering

問題

  • 地面に大きさH×Wの四角形の穴が開いている
  • 何枚かの四角形の板があり、それぞれの大きさが与えられる
  • 板を何枚か使って地面の穴を完全に覆いたい
  • ただし板の四隅が穴の外側になるように置くこと
  • 最低何枚必要か求める

方針

Div1 Medium (500) CandyCollection

問題

  • 形がN種類の飴がある
  • それぞれの形で2種類の味がある
  • 味は全部でN種類
  • それぞれの種類で、それぞれの味の在庫の数が与えられる
  • 買うときには形しか指定することができない
  • 全ての種類の味の飴を集めるのに買う必要のある個数を求める

方針

  • kmjpさんのを写経
  • 欲しくない味の個数+1を買えば欲しい味が手に入る
  • 両方の味が欲しいときはそれぞれの味の個数+1の最大値
  • それぞれの味は2回だけ出現するので、ある形で買わないと、別の形では買う必要がある
  • 同じ味でグラフでつないでいき、買う・買わないでDP
  • 形X(味A,味B) -> 形Y(味B,味C)という遷移で、味Cを買う・買わないを作っていく
  • 味Cを買わない場合は、(Xで味Bを買わない+今回味Bを買う)と(Xで味Bを買った)の最小値
  • 味Cを買う場合は、(Xで味Bを買った+今回味Cを買う)と(Xで味Bを買わない+今回両方買う)の最小値
  • 最終的に、最初に買わなかったかつ最後に買った、と、最初に買ったかつ最後に買わなかった、の最小値
  • 閉路になってるので、閉路がなくなるまでループする
  • https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_629/CandyCollection.cpp

結果

o-- 222.61pts 128th/627 rating 1520 -> 1613 (+93)

割と好調。チャレンジは速度が足りなかった。

http://togetter.com/li/705603

CandyCollection=かんこれ?

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