GCJJ 予選に参加してみた

Haskell

x86/64 最適化勉強会中に、iPad からリモートで家の PC に接続して、そこでやってました。
GCJJ に集中しすぎて勉強会の方を全然聞けなかったっていう･･･ほんとすみません。


ということで A と C が解けました。
B は満足度優先で探してたのですが、それだけだとダメだったようで･･･で、家に帰ってからいくつか修正したのですがそれでも通らなかったので根本的に考え方が間違ってるようです。で、一位の人のコード読んだら何でこれで解けるんだろうという謎のコードでした。


A のコードです。

import System (getArgs)

type Value = Int
type Index = Int
type Size = Int
type Chunk = (Index,Size)

getValue :: Int -> [Chunk] -> Index -> Value
getValue m cs ix = foldr (get m) ix cs
  where
    get :: Int -> Chunk -> Index -> Index
    get m (i,s) ix | 0     <= ix && ix < s     = ix+i
                   | s     <= ix && ix < (s+i) = ix-s
                   | (i+s) <= ix && ix < m     = ix

{-
0 <= W < M
0 <= A < M
1 <= B <= M
-}
getInput :: FilePath -> IO [(Int,[Chunk],Index)]
getInput file = readFile file >>= return.parse.lines
  where
    parse :: [String] -> [(Int,[Chunk],Index)]
    parse (num:ls) = take (read num) (parse2 ls)
    parse2 :: [String] -> [(Int,[Chunk],Index)]
    parse2 (l:ls) = (m,chunks,w-1):parse2 ls'
      where (m:c:w:_) = map read (words l)
            (chunks,ls') = parse3 c ls
    parse3 :: Int -> [String] -> ([Chunk],[String])
    parse3 num ls = (take num (map toChunk ls),drop num ls)
      where toChunk str = (i-1,s) where (i:s:_) = map read (words str)

output :: Int -> Value -> IO ()
output n v = putStrLn $ "Case #"++show n++": "++show (v+1)

main = do
  inputFile <- getArgs >>= return . head
  results <- getInput inputFile >>= return . map (\(a,b,c) -> getValue a b c)
  mapM_ (uncurry output) $ zip [1..] results

見つけたいインデックスの位置だけを監視しておいて、そこから逆順に戻していけば初期状態での位置が分かるから解けるということはすぐ分かったのですが、なぜか逆順ではなく正順でやってしまって誤答2回。素晴らしいことにサンプル入力のテストは通りました。これを見越してわざとそういう入力にしたのかと思うとムキー！という感じですね（実際はそうじゃないみたいですけど）。
でもって A 番目が 0 オリジンだと思ってて間違ったという素晴らしいこともやってしまって、ついカッとなって入力を 0 オリジンに書き換えてしまいました。
あと Haskell で入力をパースするのめちゃめちゃめんどいです。もっと Haskell にやさしい入力をお願いします。


C のコード。

import System (getArgs)

nearPower2 0 = 0
nearPower2 x = 2^(near 0 x)-1
  where
    near a x | 2^a-1 > x = a-1
             | otherwise = near (a+1) x

countBits 0 = 0
countBits x =
  let (r,q) = x `divMod` 2
  in q + countBits r

solve :: Integer -> Integer
solve x =
  let a = nearPower2 x
      b = x-a
  in countBits a + countBits b

getInput :: FilePath -> IO [Integer]
getInput file = readFile file >>= return.parse.lines
  where
    parse :: [String] -> [Integer]
    parse (num:ls) = take (read num) (parse2 ls)
    parse2 :: [String] -> [Integer]
    parse2 ls = map read ls

output :: Int -> Integer -> IO ()
output n v = putStrLn $ "Case #"++show n++": "++show v

main = do
  inputFile <- getArgs >>= return . head
  results <- getInput inputFile >>= return . map solve
  mapM_ (uncurry output) $ zip [1..] results

N に一番近い 2^n-1 の値を a として、N-a を b として、それぞれのビット数を数えたら何となく正解しました。
数学的なこととか全く考えず、単なる直感だったのですが意外にサクッと解けました。