SRM513

TopCoder

ちょっとした辱めを受けたSRM。

  • -

250. YetAnotherIncredibleMachinet

問題：落下してくるボールが一個もぶつからないような板の配置は何通り?

  • ボールの落下を全て受け止める問題だと思い込んで、しばらく悶絶した
  • 冷静になって問題文を読み直したら簡単だった
  • 板ごとに何通り配置の方法があるか計算して、全部かけるだけ
  • Mount点がどのボールの間にあるか調べて数式で出す作戦に出ることにした
    • 両端のボールの処理を簡単にするために、離れたところにもボールを配置
    • したところ、十分に離れてなくてシステムテストで落ちた＼(^o^)／
  • 終了後に俺の250が見られてる的な表示が出るたびに、恥ずかしい気持ちになった

500. PerfectMemory

問題：ぱない記憶力を持つ人がN*M枚のカードで神経衰弱をやるときに、全カードを取るまでにかかるターン数の期待値を求める

  • 夏合宿あたりでこんな問題を見たことがあるような…。
  • と思いつつ、どうせ確率DPだろうし頑張って考える。
    • 中身知ってるカードの枚数と、謎のカードの枚数あたりで状態を作る
    • 中身知ってるカードを見ても無意味なので、裏返すカードは謎のカードから
    • どこかで見たカードを引いたらペアを取る
    • そうじゃなければ謎のカードからもう一枚裏返す
      • 偶然ペアが出来たらありがたく場から除く
      • 2枚目が知ってるカードだったら次のターンで美味しく頂く
      • どちらでもなければ知ってるカードが2枚増えるだけ
  • 実装難度を下げるべくメモ探索で書いてみた。
  • 何というか苦しい感じの実装になったけど通ったので良かったことにする。

Challenge Phase

  • 250とか落ちる要素なさそうだしなぁ…と、この頃は思っていた
  • -

結果：WA / AC / -- ，+0, 364.90pt, 149位
レーティング：2314 -> 2292


「十分大きな数字」が十分大きくなかったという…。
今日は、こんなのが赤くてゴメンなさいと謝罪せざるを得ない感じでした。