Facebook Hacker Cup 2017 qual. in Haskell

今年第一次用 Haskell 打比賽,來記錄一下題解。


Haskell 是用 IO monad 來處理輸入輸出,這裡用

兩個函數去處理 IO,另外配合 readshow

read 使用上要指定 type 否則會讀爛,比如

如果要處理讀 n 筆 case 的狀況下,可以利用 Control.Monad 內的 replicateM 讀入 n 筆資料

此外,針對 n 筆資料輸出,可以考慮 mapM_ 函數

和上面讀 Int 的程式碼結合,就可以結構化造出 n 行版的輸入

在此例中,會先讀入 n,接著 readCase 處理每筆 Case 的格式,會得到 m [a] 的資料,接著往下串,針對每筆測試資料用 solve 處理,最後利用 printCase 輸出每筆測資的格式,mapM_ 最後會將 type 轉為 IO ()

因此我們只要專注在完成 readCasesolveprintCase 即可。

Hacker cup 中在輸出格式上要印出 case number,只要在解完答案後,針對每筆測資 zip 編號,微調 printCase 的格式,概念如下:


第一題給你在 (0,0) 到 (100,100) 之間的區域中,一個以 (50,50) 為中心,以 (50,50) 至 (50,100) 的向量為起點,順時針展開 P% 的扇形,每次問點 (X,Y) 是否在扇形中?

此題我是將扇形轉換到 (0,1) 逆時針展開的單位圓上,求出轉換過後的 (X,Y) 和原點的角度、長度去判斷。不難看出轉換公式為

轉換過後的座標塞入 atan2 判斷角度,只是要注意 atan2 的值域是 [-pi,pi),因此進到三四象限要補上 2 * pi


第二題,給你 N 個物品,每個物品重 Wi,接著將物品分為 k 個有序數列,每個數列的總價值為「第一個物品重 × 物品個數」,問每個數列總價值不小於 50 的前提下,k 的最大值。

此題採用 greedy 的想法,如果要分盡量多堆,那麼就讓重量最大的物品放在數列第一個位置,後面隨便塞。因為重量越大,只要越少的物品就能讓數列總價值超過 50,所以找出每個物品需要多少數量物品,排序後求前綴和小於 N 的 index 即可。

排序函數 sortData.List 中就有。核心算法實作如下:


第三題是比較有趣的題目,因為在 Haskell 實作上依然簡潔。

給定 S 個公正骰子,骰子只有 4,6,8,10,12,20 面骰,對每個骰子指定種類、骰 X 次求和,最後結果總和位移 Z 後,求此 S 個骰子值不小於 H 機率和的最大值。

此題要處理兩件事:

  1. 資料格式
  2. 計算機率

第一件事,因為每個骰子的格式為 "XdY+Z" 或 "ZdY-Z",因此我採用 regular expression 手爆。

因為在將數字從字串轉為 Int 的過程中,"""+2"等狀況下會爛掉,因此要分 case 處理。

接著處理機率問題,這裡採用生成函數的想法,機率表示在前面的係數、生成函數的冪次為點數,建構好多項式的基本操作後就可以無腦計算了。

首先是一個 n 面骰各點數的機率 gfDice

接著為了很好處理兩個生成函數相乘,寫了一個 gfPad,可以將一個生成函數依照兩個 Int 決定後來生成函數的長度、位移多少,不足的係數補 0。

決定兩個生成函數相乘,可以知道 n 次多項式和 m 次多項式相乘為 n+m 次,將 xs 每個係數和 ys 相乘順便紀錄位移,利用 gfPad 產生一堆相同長度的生成函數就可以颯爽疊起來求和。

為了方便我們對一個骰子的機率做 X 次方,寫了 gfExp

解決完以上難題後,可以發現 Z 可以反過來對 H 操作,這樣每個骰子骰 X 次後的機率分布都會一模一樣,建表解決一切。

因此題目變成,對於每種骰子骰 X 次,值不小於 H - Z 的機率和最大值。

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.