前往
大廳
主題

ZeroJudge - g015: 老鼠愛反悔 解題心得

Not In My Back Yard | 2021-06-26 00:00:08 | 巴幣 0 | 人氣 216

題目連結:


題目大意:
輸入給定一個非負整數 t (t < 2 ^ 64)以及兩個機率值 a 、 b(0 ≦ a 、 b ≦ 1),代表當前狀態如果是交易成功之狀態,則下一秒有機率 a 會變為交易失敗;反之,如果目前是交易失敗的狀態,則有機率 b 會變為成功。

已知一開始(t = 0)時,狀態為交易成功。試問 t 秒後,交易成功的機率為何?請四捨五入至小數點第二位後輸出。



範例輸入:
範例輸入 #1
1 0.55 0.45

範例輸入 #2
1000000000 0.12 0.79

範例輸入 #3
25830031103833600 0.29 0.49


範例輸出:
範例輸出 #1
0.45

範例輸出 #2
0.87

範例輸出 #3
0.63


解題思維:
因為一開始的狀態為交易成功。所以我們可以將成功 & 失敗的機率分布寫成一個 2 × 1 陣列 D =
1
0
接著使用如下 2 × 2 的轉移矩陣(Transition Matrix) P =
1 - a   b
 a   1 - b
其四個位置由上往下、由左至右的意涵為「成功變為成功」(即不變)、「失敗變成成功」、「成功變成失敗」以及「失敗變成失敗」這四個機率。

根據轉移矩陣的特性,我們可以得到第 t 秒的成功與失敗機率分布為
D' = P ^ t × D
(注意這個結果跟 D 的維度是一樣的,即 2 × 1)

而所求是問成功的機率,因此為 D' 的兩個元素中在上面的那一個元素。又因為一開始的 D 只有上面那一項為 1 ,所以所求恰好為 p ^ t 這個矩陣左上角的那個元素值。

至於 p ^ t 的求法則需要快速冪來加速(原理可以參見這題中間的說明),不然直接計算會因為 t 值太大而超時。

最後,要注意浮點數誤差會因為矩陣的次方值越大而累積得越大。所以當前一次迭代的轉移矩陣裡面元素的值與這一次的相差不遠(差值小於 10 ^ (-5) 等等)就視為這次的計算等同於誤差,因此不更動前一次的矩陣內容。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作