A - 動物園
子供がいくらで大人がいくらなので団体の入場料はという問題。問題文にある通りに計算すればよい。
main :: IO () main = getContents >>= print . solve . map read . words solve :: [Integer] -> Integer solve [ a, b, c, k, s, t ] = a * s + b * t - if s + t >= k then c * (s + t) else 0
B - 自動ドア
閉まりそうで閉まらない自動ドアの問題。人が立て続けに来たらいつまでも閉まらない。
main :: IO () main = getContents >>= print . solve . map read . words solve :: [Integer] -> Integer solve (_:t:as) = go 0 0 0 as where go n k l (x:xs) | l < x = go (n - k + l) x (x + t) xs | otherwise = go n k (x + t) xs go n k l [] = n - k + l
C - 民族大移動
それぞれの民族に対して貪欲に動いていけばいいだけです。
import Control.Applicative ((<$>), (<*>)) import Control.Monad (replicateM) main :: IO () main = getInts >>= \[_, d, k] -> solve <$> replicateM d getInts <*> replicateM k getInts >>= mapM_ print getInts :: IO [Int] getInts = map read . words <$> getLine solve :: [[Int]] -> [[Int]] -> [Int] solve lrs = map (f lrs) where f ([l, r]:rest) [s, t] | s < t && l <= s && r < t = 1 + f rest [max s r, t] | s < t && l <= s = 1 | s < t = 1 + f rest [s, t] | s == t = 0 | t < s && s <= r && t < l = 1 + f rest [min s l, t] | t < s && s <= r = 1 | t < s = 1 + f rest [s, t] f _ _ = 0
D - 動的計画法
コンテスト中は解けなかった。id:kmjp様の解答が美しすぎたのでそのままHaskellにしてみた。Pythonのpow()
相当の関数を用意しなくてはいけないけど、この解法はかなりシンプル。moduloに惑わされず、まずは普通に式で表して、それから演算をmoduloのものにすればいいんですね。こういうのをちゃっかり解けるようになりたい。
main :: IO () main = getContents >>= putStrLn . unwords . map show . solve . map read . words solve :: [Integer] -> [Integer] solve [ a, b, c ] = [ (b * c - a * c) * power (b * a - b * c + a * c) (m - 2) m `mod` m , (b * c - a * b) * power (c * a - b * c + a * b) (m - 2) m `mod` m ] where m = 1000000007 power :: Integer -> Integer -> Integer -> Integer power k 1 m = k `mod` m power k n m | even n = (power k (div n 2) m ^ (2 :: Int)) `mod` m | otherwise = (power k (div (n - 1) 2) m ^ (2 :: Int) * k) `mod` m
まぁ、Haskellは演算子を自分で定義できるのが本当に最高って感じがするし、演算子をきちんとインポート制御できるのはやっぱり最高って感じだ。以下のコードでもACであるし、式を本当にそのままコードにするだけだ。
import Prelude hiding ((*), (/), (^)) import qualified Prelude as P main :: IO () main = getContents >>= putStrLn . unwords . map show . solve . map read . words solve :: [Integer] -> [Integer] solve [ a, b, c ] = [ (a / c) / (a / b + a / c - 1) - 1, (a / b) / (a / b + a / c - 1) - 1 ] m :: Integral a => a m = 1000000007 (*), (/), (^) :: Integral a => a -> a -> a infixl 7 * x * y = x P.* y `mod` m infixl 7 / x / y = x * y ^ (m - 2) infixl 8 ^ _ ^ 0 = 1 k ^ 1 = k `mod` m k ^ n = (k ^ div n 2) P.^ (2 :: Int) * k P.^ fromEnum (odd n)