hotpepsiの練習帳

SRM 533 Div2

02:29

Easy (250) PikachuEasy

問題

• ぴかちゅーは ぴ か ちゅー しかしゃべれない。
• 与えられた文字列がぴかちゅーが発音できるものかどうかを求める。

方針

• 1文字ずつ見ていくだけ
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_533/PikachuEasy.cpp

Medium (500) CasketOfStarEasy

問題

• 星の器は東方銀河のエネルギー生成装置である。
• N個の器のそれぞれに星が格納されており、それぞれの重さが配列が与えられる。
• エネルギーの生成は、位置xを選択することで行う。
• 位置xの星を消滅させると、位置x-1と位置x+1の重さの積のエネルギーが得られる。
• 得られる最大のエネルギーを求める。

方針

• メモ化再帰
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_533/CasketOfStarEasy.cpp

Hard (1000) MagicalGirl

問題

• 魔法少女がN人の悪い魔女と戦う。
• ライフの初期値はMで、毎日1ずつ減る。
• 魔女はday[i]の日に出現する。
• 魔女に勝つ確率はwin[i]%で、勝つとライフがgain[i]増える。
• ただしライフの最大値はMである。
• 魔法少女の生存日数の期待値を求める。

方針

• 期待値DPらしい
• わからないのでAnalysisを読む
• ある一日に複数の魔女が出現する場合が問題
• ライフは増えるかゼロになるかだけなので、戦う順番は期待値に影響しない
• なので日付順に処理していってよい
• メモ化再帰 (std::mapだとTLEした)
• https://github.com/firewood/topcoder/blob/master/srm_5xx/srm_533/MagicalGirl.cpp

結果

244.96 + 242.99 + 50*2 = 587.95 188th rating 1123 -> 1152

ナイスな問題。

easyは進めていくだけなのだけど、challenge phaseでJavaの人がreplaceAllしていたので、2撃墜した。ケースを事前に予測できてたらなおベターだと思った。easyは解くのより撃墜のほうが楽しいかも。文字列処理の典型的なミスり方は、(プロコン以外の)一般的なコーディングとしても参考になる。

mediumは順番を考慮する方法が思いつかなかったのでbitのメモ化再帰。div1easyの制約条件だと通らない。40分くらいかかってチャレンジなかったらレート下がるくらいの感じだった。easyが簡単かつ典型問題だと上位は厳しい。

hardはなんとなく解法を予想しただけ。残り時間がなかったのでmediumの見直しの時間に充てた。