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 .mapMaybe (`lookup` m) $ cs
where ds = nub cs
b  = max 2 $ genericLength ds
m  = zip ds (1::[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 <  then  else x
tMin (:_)   = 
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]) $ :qs
bM = memo2 b
b i j | i == j = 
| 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 似ていると思った．

コンテンツ

A

B

C