hotpepsiの練習帳

SRM 601

greedy | 22:22

Div1 Easy (250) WinterAndPresents

問題

• りんごとみかんが入っている袋がいくつかある
• それぞれの袋からX個取り出す
• りんごとみかんの数の組み合わせが何通り可能かを求める

方針

• 任意のX個取り出す場合について考える
• それぞれの袋から、取り出せるみかんの最小個数と最大個数を集計する
• 最大-最小+1通り取り出すことができる
• Xを1から試していき、X個取り出せない袋があったら終了
• Passed System Test
• (書き直し)
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_601/WinterAndPresents.cpp

Div2 Easy (250) WinterAndMandarins

問題

• みかんの入った袋がある
• K袋選ぶ
• みかんが入っている個数の差の最小値を求める

方針

• ソートする
• 先頭のK個に着目する
• K個の末尾と先頭の差を求める
• スライドしていき最小値を求める
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_601/WinterAndMandarins.cpp

Div2 Medium (500) WinterAndCandies

問題

• 何種類かのキャンディーがある
• キャンディーの種類は正の整数
• K個取り出す
• 1からKまでの種類が揃うのは何通りか求める

方針

• 同じ種類で別のキャンディーは別物として数えるっぽい
• 種類ごとに配列cにカウントしておく
• 3種類の場合c[1]×c[2]×c[3]通り
• 全体としてはc[1]＋c[1]×c[2]＋c[1]×c[2]×c[3]...となる
• 歯抜けになる場合は、途中のカウントがゼロになるので問題ない
• K=1から足してかけて...としていく
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_601/WinterAndCandies.cpp

結果

o-- 118.42pt 513rd/767 rating 1297 -> 1298 (+1)

提出したときは、最初にXの最大値を求めた。条件を分離するのは悪くないけどタイプ数としては無駄だった。あとK=0から足してつじつまが合わなくなり最後に1ひいてださかった。

冬はこたつみかんですね。

http://togetter.com/li/605805