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 == 0   = count (a+1) b sa sb es
                              | otherwise = count a b (sa-1) sb es
count a b sa sb ((Dpt, B):es) | sb == 0   = 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 == 0   = count (a+1) b sa sb es
                              | otherwise = count a b (sa-1) sb es
count a b sa sb ((Dpt, B):es) | sb == 0   = 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 0 0 0 0.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