Hatena::Grouptopcoder

hotpepsiの練習帳

2014-03-23

SRM 601

| 22:22

Div1 Easy (250) WinterAndPresents

問題

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

方針

Div2 Easy (250) WinterAndMandarins

問題

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

方針

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

ゲスト



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