hotpepsiの練習帳

SRM 515 Div2

02:19

Easy (250) FortunateNumbers

問題

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

方針

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

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_515/FortunateNumbers.cpp

Medium (500) RotatedClock

問題

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

方針

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

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_515/RotatedClock.cpp

Hard (1000) NewItemShopTwo

問題

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

方針

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

実装

• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_515/NewItemShopTwo.cpp

結果

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

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

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