SRM 349

また遅刻した。１０分前通知じゃ遅いな・・・。

さて、しょうがないので別のプログラムでも書きながら観戦してたわけですが、みんなどんどん submit しちゃう。どんな簡単な問題セットだよとおもって、challenge が始まったとたん succeeded の嵐。そして、結局３人しか passed しなかったという波乱だったわけですね。あとで解きましたが、これが通らない。submit がすごかった真相は、サンプルがショボくて、sample 通ったくらいじゃ全然ダメでしたということだったようです。結局、さっぱりお手上げになって tomek ソースを読んだら、目から鱗の感動的ソース。あんまり 1000 点に手を出したことない私ですが、かなりの良問だったかと。

問題は読んでもらうとして。確率の問題です。

まず思いつくのは、赤玉が残り r こ、青玉が b このとき、次のボールの色 m_i の確率分布 P(m_i | r, b) が分かるので、勝つ確率が argmax と再帰で解けるよね。で、最初に取り除かれたボールの組み合わせ {R} の事前分布が分かるので、これを周辺化すればいいのねと思うと間違い。「最初にランダムに removed 個のボールを取り除き、のぞいたボールを確認してから最適戦略をしたときの勝率」になってしまう。というか、最初これやりました・・・。

このあと、各ステップごとに周辺化すればいいんだから、今まで取り除いたボール {m} と {R} が given のときの m_i の分布が分かればいいのかとなって、 P(m_i | {R}, {m}) をさっき求めたこと（要は、残りの玉の数が given）を思い出します。あとは、毎回 {R} を周辺化すればいいのか、やったね解けたと思ったところで寒気がしてきます。あれ？　必要なの P({R}) じゃなくて P({R} | {m}) じゃね？　なにこれわかんねぇよ！！

私はここで完全に混乱して、あきらめて tomek ソースを読んで愕然としました。つまり、実は {R} を周辺化する必要なんてそもそもなくて、{m} から簡単に求まるよ。いわれてみれば当たり前。高校数学ものなわけです。「赤玉が r こ、青玉が b こあります。ランダムに N こ取り除きました。次に n こ取り除いたら、赤が m_r こ、青が m_b こでした。その次の玉の色が赤の確率は何でしょう」もっと簡単に言うと、「赤玉 r こと青玉 b こをランダムに並べたとき、N + 1 番から N + n 番に赤が m_r こ、青が m_b こでした。その次の玉が赤の確率は何でしょう」

こういうプログラムと直接関係ないところでの直感力が、すごく負けている気がした日でした。