hotpepsiの練習帳

SRM 629

02:05

Div1 Easy (250) RectangleCovering

問題

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

方針

• 四隅が外側ということは、はみだす必要があるので、少なくともH+1またはW+1の長さが必要(サンプル3から、+2ではなく+1でよいことがわかる)
• H+1の長さの板を縦に並べてW以上を作るか、W+1を並べてH以上を作る2択
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_629/RectangleCovering.cpp

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=かんこれ?