当初の方針
ちょっと前に友達と一緒に学校で解いていた思い出が蘇る。
そのときはさっぱりで、解説放送を見てもさっぱり。
今もさっぱり。
解説を読んで
??????
コードが書けるようになるまで丸一日費やした。
他のブログでは独自の解釈で解説を書いているみたいなので、
このブログでは、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番目に今までのより大きい値が出る個数をカウントしてみた。
全体の数が、nP1 = n, nP2 = n(n-1), nP3 = n(n-1)(n-2)
なので、確率は、1/1, 1/2, 1/3 となっている。
これをWolframAlphaに食わせると、これ以降も1/4, 1/5 ... となるのが確認できた。
きっとこれが一般にも成り立つのだろう。よくできてるなあ。
(高校数学の範囲なのかもしれませんが・・・)
さらに補足:
先の図より、i番目に今までのより大きな数が出てくる個数は、
で表される。
こんなページを見つけた。
http://izumi-math.jp/F_Nakamura/kotewaza/sigma/sigma.htm
こういうときは、差を持ち出して計算するといいらしい。
やってみると、
で、全体の数はなので、1からnの順列において、
i番目で今までのより大きな数字が出る確率は、となる。
証明できた・・・。