AtCoder Regular Contest 055 B : せんべい

arc055.contest.atcoder.jp

当初の方針

ちょっと前に友達と一緒に学校で解いていた思い出が蘇る。

そのときはさっぱりで、解説放送を見てもさっぱり。

今もさっぱり。

解説を読んで

??????

コードが書けるようになるまで丸一日費やした。

他のブログでは独自の解釈で解説を書いているみたいなので、
このブログでは、editorialに沿ったコードでACする。

dp[i][j][b] := i枚見て、j枚食べて、全体としてmaxのせんべいを食べたか、について、id:Nのせんべいを食べた確率の最大値

と定義する。

こうすると、

dp[N][*][1] = 全部見て、全体としてmaxのせんべいを食べた=>id:Nのせんべいを食べた確率=1

dp[i][j][b] = i-1/iの確率で今までのより小さいから食べない + 1/iで今までで最大... max(なので食べる, だが見逃す)

となる。

Submission #936365 - AtCoder Regular Contest 055 | AtCoder

i枚目のとき、今までと比べて最大のせんべいがやってくる確率が、1/iというのが
イマイチ何故だかよく分からない・・・。小さいケースを手元で試してみるとその通りだけど。

確率の考え方が養えるといいなあ。何を勉強したらいいのだろう。



補足:

nの順列について、i番目に今までのより大きい値が出る個数をカウントしてみた。

f:id:arukuka:20161020203003p:plain

全体の数が、nP1 = n, nP2 = n(n-1), nP3 = n(n-1)(n-2)
なので、確率は、1/1, 1/2, 1/3 となっている。

これをWolframAlphaに食わせると、これ以降も1/4, 1/5 ... となるのが確認できた。
きっとこれが一般にも成り立つのだろう。よくできてるなあ。
(高校数学の範囲なのかもしれませんが・・・)

さらに補足:

先の図より、i番目に今までのより大きな数が出てくる個数は、


\sum_{k=1}^{n-(i-1)} k(k+1)\cdot \cdot \cdot \{ k + (i-2) \}

で表される。

こんなページを見つけた。

http://izumi-math.jp/F_Nakamura/kotewaza/sigma/sigma.htm

こういうときは、差を持ち出して計算するといいらしい。
やってみると、


\begin{eqnarray}
&&\sum_{k=1}^{n-(i-1)} k(k+1)\cdot \cdot \cdot \{ k + (i-2) \} \\
& = &\sum_{k=1}^{n-(i-1)} \frac{1}{i}\{ k(k+1)\cdot \cdot \cdot (k+(i-2))(k+(i-1)) \\
& &- (k-1)k(k+1)\cdot \cdot \cdot (k+(i-2)) \} \\
&&\\
&=&\frac{1}{i}\{1\cdot 2 \cdot \cdot \cdot (3 + i - 2) - 0\} \\
&&+\frac{1}{i}\{2\cdot 3 \cdot 4 \cdot \cdot \cdot (4 + i - 2) - 1 \cdot 2 \cdot \cdot \cdot (3 + i - 2)\} \\
&& \cdot \cdot \cdot \\
&&+ \frac{1}{i}\{ (n-(i-1)(n - (i-1)+1) \cdot \cdot \cdot (n-(i-1)+(i-1)) - 相殺される何か \} \\
&&\\
&=& \frac{1}{i} \{n-(i-1)\}\{n-(i-2)\} \cdot \cdot \cdot n \\
&=& \frac{1}{i} {}_nP_{i}
\end{eqnarray}

で、全体の数は{}_nP_{i}なので、1からnの順列において、
i番目で今までのより大きな数字が出る確率は、\frac{1}{i}となる。

証明できた・・・。