TopCoder SRM 513 Div1

LayCurseさんと同部屋。

Result

228.22 / Opened / Unopened
0チャレンジ


196位
1904 -> 1919


Mediumは簡単だったのにハマってしまって凄く残念。

Easy YetAnotherIncredibleMachine

問題

床がいくつかあって、それぞれの座標は(platformMount[i],i+1)で、長さはplatformLength[i]である。
床は左側に長さ分だけ(整数の座標を)動くことができる。


ボールがいくつか降ってくる。それぞれのボールのx座標はballs[i]である。
最初に一度だけ床を動かして、全てのボールが全ての床(両端含む)に当たらないようにしたい。


そのような動かし方の場合の数をmod 10^9+9で答えよ。

試行錯誤

いきなり面倒そうな問題。
まずはボールをソートして……って、あれこれ床の動き方全通り列挙して間に合うじゃん。
んじゃあループで書くだけ。


書いた。サンプル通った。本当に計算量が間に合うか、何度も見直して提出。
提出後適当に最大ケース作って提出。余裕で間に合う。おk

Medium PerfectMemory

問題

N行M列にカードが並んでいて、ひとりで神経衰弱する。1つのカードに対してペアになるのはただ1枚存在する。
プレイヤーが完璧な記憶力を持っていて、最善の戦略を取るとするとき、全てのカードを取るのに必要な回数の期待値を求めよ。

試行錯誤

カードは2500枚以下。ってことはdp[残りカード][記憶してるカード]みたいなDPで解けそう。
久々に簡単な500じゃん!


最善の戦略を考えると、

  • まだ不明のカードをめくる
    • 知ってるカードだったら取る
    • 知らないカードだったらもう一枚不明のカードをめくる


こんな感じ。場合分けして、コードにしてく。
できた。サンプル合わない……
いや分数の計算間違ってるし。


計算し直し。最後のちょっと大きいサンプルだけ合わない……
もしかしてあの戦略最善じゃないの?どう見ても最善のはずだろとか疑い始める。
他に良い取り方がないか50分くらい考える。


ない……よなあ。
だって不明のカードをめくらないのは、わかってるカードをめくるより絶対損だし、
不明のカードをめくった後、わかってるカードをめくるのも絶対損。


漸化式の、知らないカードをめくって、2枚目が知っているカードだった場合を書き間違っていることに気付いた!!
やばい残り2分!!
焦って直そうとするけど他のサンプルが合わなくなる。時間終了。


終了30秒後に直った。これは酷い。

Hard

あけてない。

Challenge Phase

Hardを出してる青が撃墜されていた。そのほかはチャレンジのない平和な時間。

System Test

Easyは通った。
Practiceでさっきの500を出したら通ってんの。凄く悔しい。
もっと落ち着くべきだった。