article = [snippet]

Google Code Jam Japan 2011をHaskellで解いてみた

02:34

http://code.google.com/codejam/contest/dashboard?c=889487

• 予選問題Aでちから尽きる
• Largeが一向に終わりません

{--
 - main:
 - テストの入力ファイルを標準入力から受け取り、
 - 計算後に標準出力へ解を出力する。
 -}
main = do txt <- getContents
          (printSol . sol . tail . lines) txt
-- txt :: String:   標準入力からの文字列

{--
 - テスト計算用
 - sol: テストデータ群を計算して、解のリストを返す
 - PARAM: [String]: テストの入力ファイルを一行ごとに分割したリスト
 -        [Int]:    [テスト1の解, テスト2の解, ...]
 -}
sol :: [String] -> [String]
sol []     = []
sol (t:ts) = cardStr : sol rs
  where
    -- [カードの枚数, シャッフル回数, 解となる上からw番目のカード]
    [m,c,w]  = (map read . words) t
    -- シャッフルで抜かれるカード位置, 枚数のリスト
    a        = map (read . head . words) abList
    b        = map (read . last . words) abList
    abList   = take c ts
    rs       = drop c ts
    cardStr  = show $ card c w
    {--
     - card: i回シャッフルしたカードの、上からj番目のカードの数字
     - PARAM: Int: シャッフル回数
     -        Int: カードの位置
     -}
    card :: Int -> Int -> Int
    card i j = (mids ++ pres ++ psts) !! (j-1)
      where
        pres = if i > 0
                 then [card (i-1) x | x <- [1..(ai-1)]]
                 else []
        mids = if i > 0
                 then [card (i-1) x | x <- [ai..(ai+bi-1)]]
                 else [1..m]
        psts = if i > 0
                 then [card (i-1) x | x <- [(ai+bi)..m]] 
                 else []
        ai = a!!(i-1)
        bi = b!!(i-1)

{--
 - printSol: 解のリストを受け取り、整形して標準出力に出力する
 - PARAM: [a]: [テスト1の解, テスト2の解, ...]
 -}
printSol :: [String] -> IO ()
printSol = putStrLn . unlines . trimSols 1
  where
    trimSols :: Int -> [String] -> [String]
    trimSols i (s:ss) = if ss == [] then [t] else t:ts
      where
        t = "Case #" ++ (show i) ++ ": " ++ s
        ts = trimSols (i+1) ss

ツイートする