Practice

去年のやつ．

Dashboard – Qualification Round 2008 – Google Code Jam

Bの問題

簡単な問題だと思う．Qualificationなんちゃらだし．

各駅での列車の出発，到着（正確には再び出発可能な状態になる）をイベントと思い，その時系列順のリストをつくる．

本質的な部分は以下．イベントリストから列車の動きをシュミレート．

count :: Int -> Int -> Int -> Int -> [Event] -> [Int]
count a b _ _ [] = [a, b]
count a b sa sb ((Dpt, A):es) | sa ==    = count (a+1) b sa sb es
| otherwise = count a b (sa-1) sb es
count a b sa sb ((Dpt, B):es) | sb ==    = count a (b+1) sa sb es
| otherwise = count a b sa (sb-1) es
count a b sa sb ((Arv, A):es) = count a b sa (sb+1) es
count a b sa sb ((Arv, B):es) = count a b (sa+1) sb es

全体．文字列から問題のインスタンスを作るのがけっこう面倒．

入出力にけっこう手間が，かかっている．もうすこし，シンプルにできないか？

import Control.Monad
import Data.List
data Action = Arv | Dpt deriving (Eq, Ord, Show)
data Train = A | B deriving (Eq, Ord, Show)
type Event = (Action, Train)
-- make event list from instance
mkEvents :: (Int, [[(Int, Int)]], [[(Int, Int)]]) -> [Event]
mkEvents (t, as, bs) = map snd.sort $ mkEpart t as A ++ mkEpart t bs B
where mkEpart t ts x = [(d, (Dpt, x)) | d <- dpts] ++ [(tournaround a, (Arv, x)) | a <- arvs]
where (dpts, arvs) = unzip.map ((x:y:zs) -> (x,y)) $ ts
tournaround (h,m) = (h + div (m + t) 60, mod (m + t) 60)
-- main part
count :: Int -> Int -> Int -> Int -> [Event] -> [Int]
count a b _ _ [] = [a, b]
count a b sa sb ((Dpt, A):es) | sa ==    = count (a+1) b sa sb es
| otherwise = count a b (sa-1) sb es
count a b sa sb ((Dpt, B):es) | sb ==    = count a (b+1) sa sb es
| otherwise = count a b sa (sb-1) es
count a b sa sb ((Arv, A):es) = count a b sa (sb+1) es
count a b sa sb ((Arv, B):es) = count a b (sa+1) sb es
main = mapM_ putStrLn.zipWith output [1..].map (count    .mkEvents) =<< (`replicateM` getCase) =<< getInt
-- output and input function
toTime :: String -> (Int, Int)
toTime s = (read.take 2 $ s, read.take 2.drop 3 $ s)
getCase :: IO (Int, [[(Int, Int)]], [[(Int, Int)]])
getCase = do t <- getInt
[a,b] <- getInts
as <- replicateM a (liftM (map toTime.words) getLine)
bs <- replicateM b (liftM (map toTime.words) getLine)
return (t, as, bs)
output :: Show a => Int -> [a] -> String
output x xs = concat $ "Case #" : show x : ": " : interleave (map show xs) " "
where interleave []     y = []
interleave [x]    y = [x]
interleave (x:xs) y = x:y:interleave xs y
getList :: Read a => IO [a]
getList = liftM (map read.words) getLine
getInts :: IO [Int]
getInts = getList
getInt :: IO Int
getInt = liftM head getInts