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, 2ab, b^2]
pos x = if x <  then  else x
tMin (:)   = 
tMin (p:q:) = pos $ - fromIntegral q / fromIntegral (2p)
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 似ていると思った.