※ 引述《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 世界を大いに盛り上げるための涼宮ハルヒの団　　　 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.230.62 ※ 編輯: LPH66 來自: 140.112.28.91 (02/16 16:23)