Round 1C (Google Code Jam 2009)

ヘボヘボだった，1Bだが，なんとか通過していた．

練習のために，1Cもやってみた．
時間制限とかプレッシャーがないぶん，気楽で，まぁまぁ良い感じだった（たぶん，問題も簡単になっている）．

（前回と同じテンプレートを使用しています．）

A

そのまま．ただし，1進数は許されないことに注意．

main = do n <- getInt
          forM_ [1..n] $ \i ->
              do s <- getLine
                 putStrLn.output i $ f s

f :: (Eq a) => [a] -> Integer
f cs = foldl' add 0.mapMaybe (`lookup` m) $ cs
    where ds = nub cs
          b  = max 2 $ genericLength ds
          m  = zip ds (1:0:[2..])
          add x y = b * x + y

B

微分とかできますか？って問題なんですかね．
実は，計算誤差のこと全く考えていなかった（なんとうマヌケ）．ちょっと悩んだけど，
出力みたらNaNとか負の時間とかになっていたので，そこで気づいた．

main = do t <- getInt
          forM_ [1..t] $ \i ->
              do n <- getInt
                 cs <- liftM (coef.unite).replicateM (fromIntegral n) $ getInts
                 putStrLn $ "Case #"++show i++": "++ show (dMin n cs)++" "++show (tMin cs)

unite :: Integral a => [[a]] -> [a]
unite fs = map sum.transpose $ fs

coef :: Integral a => [a] -> [a]
coef [x,y,z,vx,vy,vz] = unite.map f $ [(vx,x),(vy,y),(vz,z)]
    where f (a,b) = [a^2, 2*a*b, b^2]

pos x = if x < 0 then 0 else x

tMin (0:_)   = 0
tMin (p:q:_) = pos $ - fromIntegral q / fromIntegral (2*p)

dMin n cs = (/n').sqrt.pos.sum.zipWith (*) (map fromIntegral cs) $ [t^2, t, 1]
    where t = tMin cs
          n' = fromIntegral $ n

-- output and input function

getInts :: IO [Integer]
getInts = getList

getInt :: IO Integer
getInt = liftM head getInts

あと，Intで計算したら桁落ちしてたので，Integerにした．

C

逆から考えてDP.

囚人が抜けていくのではなく，囚人が空いているかしょに入ってくると思って再帰．
若干実行時間が，遅い気もするが，配列ではなく，メモ化再帰だから，おおめにみる．

main = do
  n <- getInt
  forM_ [1..n] $ \i ->
      do (p:q:_) <- getInts
         qs <- getInts
         putStrLn.output i $ (bribe p qs)

bribe :: Int -> [Int] -> Int
bribe p qs = b 1 $ length ss
    where ss = map pred.zipWith (-) (qs++[p+1]) $ 0:qs
          bM = memo2 b
          b i j | i == j = 0
                | i <  j = b0 i j + minimum [bM i k + bM (k+1) j| k <- [i..j-1]]
          b0 i j = pred.sum.intersperse 1.take (j-i+1).drop (i-1) $ ss

結構，シンプルだと自分では思っている．やはり，MemoTrieが便利（memo2ってやつ）．

# C は 雰囲気が Project Euler #253 似ていると思った．