日々の流転

λ. Google Code Jam 2010 Round 1C

1CはなんとかC-large以外を解くことが出来た。

Rank

189

Score

76

Penalty

1:59:35

1A,1Bでパス出来ずに諦めかけていたが、ラストチャンスの1Cでなんとかなった。危なかった……

それから、Code Jam 2010 Statistics · Language Details: Haskell によると、Round 1C に参加していた Haskeller の21人の中ではトップだったらしい。ちょっと嬉しい。

• Participant Details: sakai ― Code Jam 2010 Statistic

A. Rope Intranet

両側で大小関係が入れ替わっているような組の数を数えればよいだけ。

import Control.Monad
import Text.Printf

pairs :: [a] -> [(a,a)]
pairs [] = []
pairs (x:xs) = [(x,y) | y <- xs] ++ pairs xs

f :: [(Int,Int)] -> Int
f xs = length $ do
  ((a1,b1),(a2,b2)) <- pairs xs
  guard $ signum (a1-a2) /= signum (b1-b2)
  return ()

main :: IO ()
main = do
  t <- readLn
  forM_ [(1::Int)..t] $ \x -> do
    n <- readLn
    xs <- replicateM n $ liftM ((\[x,y] -> (x,y)) . map read . words) getLine
    printf "Case #%d: %d\n" x (f xs)

B. Load Testing

元の区間を最終的に何個の領域で分割・被覆できるかを考えて、そのためには二分割を何段階繰り返せば良いかを考える。 ceiling (logBase 2 (logBase C (P/L))) みたいな値だとは思ったけど、念のため整数演算で計算。後から、naoya_tさんの記事で「対数空間で二分探索する感じ」と書いてあるのを見て、「なるほど。そうまとめられるのか」と思った。

import Control.Monad
import Text.Printf

f :: Integer -> Integer -> Integer -> Integer
f l p c = head [m | (m,x) <- zip [0..] (iterate (2*) 1), n <= x]
  where n = head [n | (n,x) <- zip [0..] (iterate (c*) l), p <= x]

main :: IO ()
main = do
  t <- readLn
  forM_ [(1::Int)..t] $ \x -> do
    [l,p,c] <- liftM (map read . words) getLine
    printf "Case #%d: %d\n" x (f l p c)

C. Making Chess Boards

ナイーブに解いたらsmallは解けた。 largeの最大サイズの入力を適当に生成して食わせてみたら終わらなかったのだけど、最適化とかを考えているうちに残り時間がなくなったので、ダメ元でlargeのデータをダウンロードしてやっぱりダメだった。 後からnaoya_tさんの記事を読んで、そうやれば良かったのかと思った。

【2010-07-07 追記】 書き直して解けた。 C2.hs