ProjectEuler 371 Licence plates - 拼圖

※ 引述《utomaya (烏托馬雅)》之銘言：
: ※ 引述《babufong (嗶嗶)》之銘言：
: : 371. Licence plates
: : http://projecteuler.net/problem=371
: : 俄勒岡州的車牌號碼是由三個英文字母後面接著三位數字(0到9)所組成的。
: : Seth 開車去上班時，他會玩一個小遊戲：
: : 每當他在路途上，看到兩個車牌號碼的數字部分相加為 1000 時，就算勝了這場遊戲。
: : (如 MIC-012 和 HAN-988，或是 RYU-500 和 SET-500，這都算勝利，只要是在同一趟
: : 車程中看到。）
: : 計算出 Seth 贏得遊戲所需要看到的車牌數的期望值，並將答案給到小數點後八位數。
: 一開始往馬可夫鏈的方面去想，結果被困了好久
以下是馬可夫鏈的解法:

(順便當防雷頁)




































設全部有 0 ~ n-1 的車牌要湊成 n 其中 n 為偶數

(原題為 n = 1000 的情形)

這個馬可夫鏈中一共有 n+1 個狀態

前 n 個對應於 utomaya 的 n 個 DP 格

(即前 n/2 個狀態是還沒看到 n/2, 後 n/2 個狀態是看到了一個 n/2)

而第 n+1 個狀態則是 "win" 是個吸收狀態

因此題目便是要求這個馬可夫鏈的"平均吸收次數"

先寫出它的轉移矩陣:

對 1≦i≦n/2, 狀態 i 代表看到了 i-1 組的數字之一但沒有 n/2

於是有 i 個情形停在狀態 i, 有 n-2i 個情形進入狀態 i+1,

有 1 個情形進入狀態 i+n/2, 有 i-1 個情形進入狀態 "win"

而狀態 i+n/2 代表看到了 i-1 組的數字之一且有一次 n/2

於是有 i 個情形停在狀態 i+n/2, 有 n-2i 個情形進入狀態 i+1+n/2,

有 i 個情形進入狀態 "win"

(當 i = n/2 時沒有進入狀態 i+1+n/2 的部份, 不過這個馬上可以處理)

所以它的轉移矩陣長這樣:

[ 1 n-2 1 0 ]
[ 2 n-4 1 1 ]
[ 3 n-6 1 2 ]
[ ... ... ... ]
[ n/2-1 2 1 n/2-2 ]
１ [ n/2 1 n/2-1 ]
---- [ 1 n-2 1 ]
ｎ [ 2 n-4 2 ]
[ 3 n-6 3 ]
[ ... ... ]
[ n/2-1 2 n/2-1 ]
[ n/2 n/2 ]
[ n ]


可以看到扣除吸收的那個狀態

剩下的部份左上和右下是一樣的雙對角線矩陣 左下是 0 右上是 I/n

也就是這部份可以寫成

Q = [ Q' I/n ]
[ 0 Q' ]

參照 http://en.wikipedia.org/wiki/Absorbing_Markov_chain

我們可以計算其基本矩陣 N = (I-Q)^-1

計算結果是

N = [ (I-Q')^-1 (1/n)((I-Q')^-1)^2 ]
[ 0 (I-Q')^-1 ]

而平均吸收時間即為 N 乘上 1 向量

因此題目所求即為 N 矩陣的第一列的和

於是剩下的就是計算出 (I-Q')^-1 及其平方 這也很容易

因為 I-Q' 只有兩個對角線有值

因此直接以擴張矩陣 [I-Q' | I] 做倒回代換即可求得

其元素為

n j-1 n-2k
A_{i,j} = --- * Π ---- , i≦j (是個上三角矩陣)
n-j k=i n-k

由此 ((I-Q')^-1)^2 的元素為

n/2
B_{i,j} = Σ A_{1,k} A_{k,j}
k=1

n/2 n/2
因此所求即為 Σ A_{1,j} + (1/n) Σ B_{1,j}
j=1 j=1


n/2 / n/2 \
它可以化為 Σ A_{1,k} | 1 + (1/n) Σ A_{k,j} |
k=1 \ j=k /

所以程式上就先把 A 矩陣給算出來存著 (需時 O(n^3))

再套用上面這個式子 (需時O(n^2)) 就得到答案了

我猜 utomaya 被困住應該是不知道有計算"平均吸收時間"的公式...
















還是要擋一下的頁末防雷頁

--
◢ ˊ_▂▃▄▂_ˋ. ◣　　　　　 　　　　▅▅　▅▅　ι●╮　　 █▄▄▄▄▄
▍./◤_▂▃▄▂_◥ \'▊ 　　ＨＡＲＵＨＩ █████　＜■┘ 　 ▄▄▄▄▄▄▄
▎⊿ ◤◤◥█◥◥█Δ 　　ＩＳＭ　 　　By-gamejye　￠|\ 　　▌▌▌▌▌▄▌▌
▏ζ(▏●‵◥′●▊)Ψ ▏　　 　　　 　　　　█　　　 ⊿Δ 　　▄▄▄ ▄▄▄▄
█/|▊ 〃 、 〃▋ |\ ▎　　　　　 　 　ハルヒ主義　　　 　　█▄▄▄█▄▄
◥◥|◣ ‵′ ◢/'◢◢S.O.S 世界を大いに盛り上げるための涼宮ハルヒの団　　　

--