在Haskell

Question

我試圖解決在Haskell這個問題解決CHRL4的代碼廚師（廚師和方式），但codechef編譯口口聲聲說這是錯誤的答案。問題如下：

在拜訪了一個童年的朋友後，廚師想要回到他的家。朋友住在第一街，而主廚自己住在第N街（最後）。他們的城市有點特別：當且僅當1 < = Y - X < = K，其中K是給予您的整數值時，您可以從第X街道移動到第Y街道。廚師希望以所有訪問過的街道的特殊數字（包括第一街和第N街）的產品最少的方式回到家中。請幫助他找到這樣的產品。 輸入

第一行輸入由兩個整數組成 - N和K--分別爲街道數和K值。第二行分別由N個號碼組成 - A1，A2，...，AN，其中Ai等於第i條街道的特殊號碼。 輸出應模1000000007

輸入

輸出

我所用的溶液如下：

import qualified Data.ByteString.Char8 as B 
import Data.Maybe (fromJust) 


findMinIndex x index minIndex n 
     | index == n = minIndex 
     | (x!!index) < (x!!minIndex) = findMinIndex x (index+1) index n 
     | otherwise = findMinIndex x (index+1) minIndex n 


minCost []  _ = 1 
minCost (x:xs) k = let indexList = take k xs 
         minIndex = findMinIndex indexList 0 0 (length indexList) 
        in x * minCost(drop minIndex xs) k 

main :: IO() 
main = do 
     t <- B.getContents 
     let inputs = B.lines t 
     let firstLine = inputs !! 0 
     let secondLine = inputs !! 1 
     let [n,k] = map (fst . fromJust . B.readInt) $ B.split ' ' firstLine 
     let specialNums = reverse $ map (fst . fromJust . B.readInteger) $ B.split ' ' secondLine 
     putStrLn $ show ((minCost specialNums k) `mod` 1000000007) 

---

它適用於給定的測試用例和我試用的其他幾個測試用例。但它沒有被codechef接受。我跟蹤了這​​個問題的社論並做出了決定。基本上從特殊數字列表中的最後一個數字開始，程序搜索它是直接的k個前輩，並且找到該範圍中的最小數字，並將其乘以當前數值，直到列表開始爲止

Answer 1

算法不會不要總是給所有的輸入最小的產品，例如這一個：

5 2 
3 2 3 2 3 

的editorial整個說明了問題，你真的應該讀一遍。

這個問題基本上是最短路徑問題，街道是頂點，從街到街的可能移動是圖的邊，邊的權重由尾單獨的特殊值決定。由於

a * b = exp（log（a））這個問題可以通過取所有特殊值的對數來歸一化，而總的移動成本定義爲產品而不是所有成本的總和。 + log（b））

鑑於log是單調遞增函數，最小乘積只是對數的最小和。

在社論編輯挑選Dijkstra算法，但服用數變換後，這將是一個標準的最短路徑問題，可以用任何你喜歡的最短路徑算法來解決。

在Haskell中有很多Dijkstra算法的實現，我在Hackage上找到了兩個，一個是here。解析和圖形初始化代碼非常簡單。

import   Control.Monad  (foldM) 
import   Control.Monad.ST 
import   Data.Array 
import   Data.Array.MArray 
import   Data.Array.ST 
import   Data.Function  (on) 
import   Data.IntMap.Strict as M 
import   Data.List   (groupBy) 
import   Data.Set   as S 

-- Code from http://rosettacode.org/wiki/Dijkstra's_algorithm#Haskell 
dijkstra :: (Ix v, Num w, Ord w, Bounded w) => v -> v -> Array v [(v,w)] -> (Array v w, Array v v) 
dijkstra src invalid_index adj_list = runST $ do 
    min_distance <- newSTArray b maxBound 
    writeArray min_distance src 0 
    previous <- newSTArray b invalid_index 
    let aux vertex_queue = 
     case S.minView vertex_queue of 
      Nothing -> return() 
      Just ((dist, u), vertex_queue') -> 
      let edges = adj_list Data.Array.! u 
       f vertex_queue (v, weight) = do 
        let dist_thru_u = dist + weight 
        old_dist <- readArray min_distance v 
        if dist_thru_u >= old_dist then 
        return vertex_queue 
        else do 
        let vertex_queue' = S.delete (old_dist, v) vertex_queue 
        writeArray min_distance v dist_thru_u 
        writeArray previous v u 
        return $ S.insert (dist_thru_u, v) vertex_queue' 
      in 
      foldM f vertex_queue' edges >>= aux 
    aux (S.singleton (0, src)) 
    m <- freeze min_distance 
    p <- freeze previous 
    return (m, p) 
    where b = bounds adj_list 
     newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e) 
     newSTArray = newArray 

shortest_path_to :: (Ix v) => v -> v -> Array v v -> [v] 
shortest_path_to target invalid_index previous = 
    aux target [] where 
    aux vertex acc | vertex == invalid_index = acc 
        | otherwise = aux (previous Data.Array.! vertex) (vertex : acc) 


-- Code I wrote 
instance Bounded Double where 
    minBound = -1e100 
    maxBound = 1e100 

constructInput :: Int -> Int -> M.IntMap Integer -> Array Int [(Int, Double)] 
constructInput n k specMap = 
    let 
     specMap' = fmap (log . fromIntegral) specMap 
     edges = [(src, [(dest, specMap' M.! dest) | dest <- [src+1..src+k], dest <= n]) | src <- [1..n]] 
    in 
     array (1, n) edges 

main :: IO() 
main = do 
    rawInput <- getContents 
    let 
     [l, l'] = lines rawInput 
     [n,k] = fmap read . words $ l 
     specs = fmap read . words $ l' 
     specMap = M.fromList $ [1..n] `zip` specs 
     adj_list = constructInput n k specMap 
     (_, previous) = dijkstra 1 0 adj_list 
     path = shortest_path_to n 0 previous 
     weight = (product $ fmap (specMap M.!) path) `mod` 1000000007 
    print weight 

PS：我的方案得分30有很多TLE的（以下簡稱「太長執行」我猜）上CodeChief，爲全面標記，你可以有自己嘗試一下，並得到較好的解決。