読者です 読者をやめる 読者になる 読者になる

Code Jam Japan 2011 予選

Haskell GCJ

ずっとcodeforcesもやってないし, たまにはこういうのやらなきゃなぁと思いつつ...


全然駄目ぽ(´・ω:;.:...


AのsmallとCのsmall/largeが正解でした...


とりあえずCの自分の解答

main = interact $ format . map solve . parseInput

parseInput = tail . map (map read . words :: String -> [Int]) . lines

format :: (Show a) => [a] -> String
format = unlines . map f . (zip [1..])
  where show_ :: (Show a) => a -> String
        show_ x | ((=='"') . head . show) x = init $ tail $ show x
                | otherwise                 = show x
        f :: Show a => (Integer, a) -> String
        f  = \x -> "Case #" ++ show (fst x) ++ ": " ++ show_ (snd x)

solve (x:_) = solv $ spl $ binary x

spl "" = []
spl x = [(length ones, length zeros)] ++ spl bs
  where (ones, as) = span (=='1') x
        (zeros, bs) = span (=='0') as

solv [(a, b)]
  | b == 0    = a
  | otherwise = 2 * a + b - 1
solv ((a, b):xs@((c, d):xss))
  | d == 0    = 2 * a + b - 1 + solv xs
  | otherwise = 2 * a + b + solv xs

binary :: Int -> String
binary 0 = "0"
binary 1 = "1"
binary n = let (k, b) = n `divMod` 2 in binary k ++ show b

オーダーとかよく分かんないや...


まぁlarge通ったのでよしとしましょう