Re: [中譯] ProjectEuler 371 Licence plates

看板puzzle (益智遊戲 - 數獨,拼圖,推理,西洋棋)作者LPH66 (-858993460)時間14年前 (2012/02/14 19:34)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串3/3 (看更多)

※ 引述《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