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

AtCoder Beginner Contest 024

atcoder

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にしてみた。Pythonpow()相当の関数を用意しなくてはいけないけど、この解法はかなりシンプル。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)