これからもたまにはコンテスト参加しよう。あたしがんばるもん。まぁ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
解いていない。
