推 jurian0101:機率和組合最頭大了~ 02/13 17:00
推 LPH66:其實馬可夫鏈就只是一口氣做很多次 DP 而已... 02/14 15:51
※ 引述《babufong (嗶嗶)》之銘言：
: 371. Licence plates
: http://projecteuler.net/problem=371
: 俄勒岡州的車牌號碼是由三個英文字母後面接著三位數字(0到9)所組成的。
: Seth 開車去上班時，他會玩一個小遊戲：
: 每當他在路途上，看到兩個車牌號碼的數字部分相加為 1000 時，就算勝了這場遊戲。
: (如 MIC-012 和 HAN-988，或是 RYU-500 和 SET-500，這都算勝利，只要是在同一趟
: 車程中看到。）
: 計算出 Seth 贏得遊戲所需要看到的車牌數的期望值，並將答案給到小數點後八位數。
一開始往馬可夫鏈的方面去想，結果被困了好久
最後靈光一閃，發現了其實只是個簡單的DP題
車牌英文字母不重要, 因為對每一個數字來說，每一種3位英文字母出現的機率相等
所以問題簡化成只有數字相加
要加成1000, 一共有1+999, 2+998, 3+997, ...., 499+501, 500+500；500種配對
500比較特殊，要另外討論，所以是499個數字配對和跟有沒有500
DP的狀態是500*2
表示499對數字中,有幾對已經在「聽牌狀態」了，跟有沒有500數字在其中，所以是500*2
已出現的數字是{2,3,499}跟{7, 23, 888}沒有不同，在DP上，都是屬同一個狀態
皆是表示有3對數字在「聽牌狀態」
「聽牌狀態」是我發明的辭，表示一個數對已有其中之一被看到，
在等待另一個數字湊成1000
接下來是求取每一次看見車牌，還無法湊成1000的機率
假設在第n次看見車牌後，還無法湊成1000的機率為p_n(註: 用 _ 表示下標)
很顯然的
在前一次尚未湊成1000，而在這次湊成1000的機率為(1-p_n)-(1-p_(n-1))=p_(n-1)-p_n
期望值為 sigma(2<=n=∞) (p_(n-1)-p_n)*n
很直覺的，p_1=1
p_2以後就用DP算出
差不多算到第300次看見車牌，p_n就衰減到近乎於零
所以算到300次即可
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.62.203.103
※ 編輯: utomaya 來自: 61.62.203.103 (02/13 09:45)