Hatena::Grouptopcoder

hotpepsiの練習帳

2011-08-22

SRM 515 Div2

02:19

Easy (250) FortunateNumbers

問題

  • 5と8がラッキーナンバー
  • 3つの数の和がラッキーナンバーだけでできている値の個数を数える

方針

  • 二重ループでaとbの和をsetに突っ込んでおく
  • (aとbの和)とcの和をsetに突っ込む
  • 最後の集合がラッキーナンバーか判定

実装

Medium (500) RotatedClock

問題

  • 数字が書いていない時計の時刻を当てる

方針

  • 短針が30度を超えていたら30度戻す (最小値を求めるためだが、一意に求まるので不要だった)
  • 短針を30度ずつ加えていき、時刻として成立しているかどうか調べる

実装

Hard (1000) NewItemShopTwo

問題

  • アイテムショップに商品が1つだけある。
  • 客が2人いて、それぞれの客は一日に一回だけ来る。
  • それぞれの客が来る時刻、購入価格、確率が与えられる。
  • アイテムショップの最大の利益を求める。

方針

  • 遅い時刻からDP
  • 他の方の回答を読んでも理解できないので、二つに分離
  • 客が一人しかいない場合の期待値earnを計算しておく
  • どちらかの客が来る時刻の期待値は、(客が来る確率×(価格ともう一方の客のearnとの大きいほう))+(客が来ない確率×(次の時刻の期待値))となる

実装

結果

oo- 181.90+390.79 rating 999→1116 easyに時間がかかりすぎたが、mediumが早めだったので大幅up。

easyは蟻本のくじの問題に似ていたので、二重ループ→ループにしてみたが、三重ループでも十分間に合ったかも。

513と514を飛ばしてしまったので、あとで解く。

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