Google Code Jam Round 1B
Dashboard - Round 1B 2009 - Google Code Jam
終わりました。
A と B の Small と Large をそれぞれ通して 56 点。とりあえず先には進めるようですが、860位というイマイチな成績でした。
今回は C が難しくて上位陣でも解いている人は少なかったので、点数が足りなかったというより時間かかりすぎたのが敗因です。速い人はだいたい1時間くらいで A と B を片づけて残りの時間で C を進めてましたが、僕は B を解き終わった時点で 1 時間、その後 A を解くのに丸々1時間半かかってしまいました。
まぁ、でも実力相応かな。
- A : またまたパーサを書く問題。二分木を作るパーサを書ければ終了。Parsec を使おうと思ったものの、使い方を全く覚えておらず、hoogle や自分の過去のコードを眺めながら必死で書く。残り10分を切ってから Small と Large をまとめて Submit。
- B : 1〜9 の数字を決められた回数使って数を生成する。足りなくなったら 0 も使ってよい。次の数がどうなるかという規則を見つければ簡単。
- C : 0〜9 の数字と(+)(-)の記号を正方形のマスに並べてあって、そこを辿って決められた数字を作る。後戻り可という条件があるために、計算を終了させる条件が思いつかず、手つかず。時間があっても解けなかったと思う。
以下に載せた A のコードなのですが、Parsec で <|> を使ってパーサを繋げるとき、インデントがだんだん深くなってしまいます。「または」という並列の条件なのでインデントも揃えたいのですが、何とかならないものでしょうか?
あと tree 関数の二つのパーサは共通部分がとても多いのですが、まとめて書けないものでしょうか?
急いで書きなぐったコードなので、他にもすっきり書けるポイントがあれば、ぜひ指摘をお願いします。
A のコード
import Numeric import Text.ParserCombinators.Parsec data Tree = L Double | T Double String Tree Tree deriving Show number :: Parser Double number = do dec <- many digit char '.' rest <- many digit return $ read $ dec++"."++rest treeCore :: Parser Tree treeCore = try (do n <- number spaces f <- many lower spaces t1 <- tree spaces t2 <- tree return $ T n f t1 t2) <|> (do n <- number return $ L n) tree :: Parser Tree tree = do spaces char '(' spaces t <- treeCore spaces char ')' spaces return t solve :: (Tree, [[String]]) -> [Double] solve (t, as) = map (solve' 1 t) as solve' d (L m) fs = d*m solve' d (T n f t1 t2) fs | elem f fs = solve' (d*n) t1 fs | otherwise = solve' (d*n) t2 fs read' :: [String] -> [(Tree, [[String]])] read' [] = [] read' (l':s0) = (t, animals) : read' s2 where l = read l' (tree',a':s1) = splitAt l s0 Right t = parse tree "" $ concat tree' a = read a' (animals',s2) = splitAt a s1 animals = map (drop 2.words) animals' show' :: Int -> [Double] -> [String] show' n ds = ("Case #" ++ show n ++ ":") : map (\d -> showFFloat (Just 7) d "") ds main :: IO() main = do input <- getContents let (c:cs) = lines input let n = read c putStr $ unlines $ concat $ zipWith show' [1..] $ map solve $ take n $ read' cs
B のコード
import Data.Char import Data.List solve :: [Int] -> [Int] solve ns | null is = solve $ 0:ns | otherwise = ns0 ++ n':ns1' where ds = zipWith (-) ns $ tail ns is = findIndices (<0) ds (ns0,n:ns1) = splitAt (last is) ns n' = minimum $ filter (>n) ns1 ns1' = sort $ n : delete n' ns1 show' :: Int -> [Int] -> String show' n a = "Case #" ++ show n ++ ": " ++ map intToDigit a main :: IO() main = do input <- getContents let (c:cs) = lines input let n = read c putStr $ unlines $ zipWith show' [1..] $ map (solve.map digitToInt) $ take n cs