Hatena::Grouptopcoder

hotpepsiの練習帳

2012-02-24

SRM 533 Div2

02:29

Easy (250) PikachuEasy

問題

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

方針

Medium (500) CasketOfStarEasy

問題

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

方針

Hard (1000) MagicalGirl

問題

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

方針

結果

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の見直しの時間に充てた。

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