読者です 読者をやめる 読者になる 読者になる

Google Code Jam 2015 Qualification Round

GCJ Haskell

これからもたまにはコンテスト参加しよう。あたしがんばるもん。まぁCodeforcesは日本時間だとつらい感じに開催されているので、寝不足にならないように程々にね?

A. Standing Ovation

左からなめて行って、足らなかったら観客を足す。足した観客はみんな拍手できるのかと一瞬思うけれど、S_i=0にみんな置けばいいので大丈夫。

import Data.Char (digitToInt)
import Data.List (foldl')

main :: IO ()
main = getContents >>= mapM_ (putStrLn . format) . zip [1..] . map (solve . map digitToInt . (!!1) . words) . tail . lines

solve :: [Int] -> Int
solve = snd . foldl' (\((n, k), r) x -> ((max n k + x, k + 1), r + max 0 (k - n))) ((0, 0), 0)

format :: Show a => (Int, a) -> String
format (k, s) = "Case #" ++ show k ++ ": " ++ show s

B. Infinite House of Pancakes

最後に一つづつ減らしていく数dに対して、それより多いやつを分けて行くのに必要な回数の総和を足す。それの最小。

main :: IO ()
main = getContents >>= mapM_ (putStrLn . format) . zip [1..] . solve . map (map read . words) . tail . lines

solve :: [[Int]] -> [Int]
solve (_:ds:rest) = solve' ds : solve rest
solve _ = []

solve' :: [Int] -> Int
solve' ds = minimum [ k + sum [ (d - 1) `div` k | d <- ds ] | k <- [1..1000] ]

format :: Show a => (Int, a) -> String
format (k, s) = "Case #" ++ show k ++ ": " ++ show s

(コンテスト中は、大きいのから半分にしていって…とか考えていて解けなかった。悔しいよ。)

C. Dijkstra

四元数を左側から掛けて行って、iとかjとかkになればOK。残ったやつを掛けたら1になるとかもOK。四元数の扱い方はなんでもいいけど、実数の四つ組にするのが一番簡単かと思われる。以下ではIntにしてるけど誤差よけのため。グラフのダイクストラ法は関係ない。

import Data.List (foldl')

main :: IO ()
main = getContents >>= mapM_ (putStrLn . format) . zip [1..] . map yesno . solve . tail . words

solve :: [String] -> [Bool]
solve (_:x:cs:rest) = solve' (map charToQuaternion "ijk")
                             ([1 .. f (read x) :: Integer] >> map charToQuaternion cs)
                             one
                    : solve rest
  where f y = min y (y `mod` 4 + 8)
solve _ = []

solve' :: [Quaternion] -> [Quaternion] -> Quaternion -> Bool
solve' [] ys _ = one == foldl' (<<>>) one ys
solve' xxs@(x:xs) (y:ys) z | x == z <<>> y = solve' xs ys one
                           | otherwise = solve' xxs ys (z <<>> y)
solve' _ _ _ = False

data Quaternion = Quaternion Int Int Int Int deriving Eq

(<<>>) :: Quaternion -> Quaternion -> Quaternion
Quaternion a1 b1 c1 d1 <<>> Quaternion a2 b2 c2 d2
  = Quaternion (a1 * a2 - b1 * b2 - c1 * c2 - d1 * d2)
               (a1 * b2 + b1 * a2 + c1 * d2 - d1 * c2)
               (a1 * c2 - b1 * d2 + c1 * a2 + d1 * b2)
               (a1 * d2 + b1 * c2 - c1 * b2 + d1 * a2)

one :: Quaternion
one = Quaternion 1 0 0 0

charToQuaternion :: Char -> Quaternion
charToQuaternion 'i' = Quaternion 0 1 0 0
charToQuaternion 'j' = Quaternion 0 0 1 0
charToQuaternion 'k' = Quaternion 0 0 0 1
charToQuaternion _ = one

yesno :: Bool -> String
yesno True = "YES"
yesno _ = "NO"

format :: (Int, String) -> String
format (k, s) = "Case #" ++ show k ++ ": " ++ s

(コンテスト中はダイクストラ法か…めんどくさそうだな…って思って問題すら開かなかった。丁寧にやれば解ける。)

D. Ominous Omino

解いていない。