AtCoder Beginner Contest 085 解き直し：Haskell による - はむ吉（のんびり）の練習ノート

昨日 AtCoder にて定期コンテスト AtCoder Beginner Contest 085 が開かれましたが，私は解くのに時間がかかったうえ， C 問題までの 3 完という，自分としてはひどい結果に終わりました *1 ．最近コンテスト後の復習が不十分だったので，今回は解き直しをしてみることにしました．なお，今回の問題では Haskell を使うと簡潔に書けそうだったので，すべてこれで解きました *2．

簡単な解説と解答コード
感想

簡単な解説と解答コード

A - Already 2018

先頭 4 文字を "2018" に置き換えれば正答を得られます．

revise :: String -> String
revise s = "2018" ++ drop 4 s

main :: IO ()
main = interact revise

B - Kagami Mochi

直径が（重複を除いて）何種類あるかを数えると，それが求める値になります．実装では， $d_1, d_2, \cdots, d_N$ を要素の重複を許さない集合に入れ，その要素数を求めると簡潔です．制約よりここでは Data.IntSet を使っています．

import Control.Monad (replicateM)
import qualified Data.IntSet as IS

maxHeight :: [Int] -> Int
maxHeight = IS.size . IS.fromList

main :: IO ()
main = do
    n <- readLn :: IO Int
    ds <- replicateM n readLn :: IO [Int]
    print $ maxHeight ds

C - Otoshidama

連立方程式 $x + y + z = N, 10000x + 5000y + 1000z = Y$ を満たす非負整数解 $(x, y, z)$ を探します．第一式を $z = N - x - y$ と変形すれば， $x, y$ のみを全探索すればよいことがわかります．実装ではリスト内包表記を用いてこれらの条件をそのまま記述しています *3．また，解が存在しない場合があるので，Maybe モナドを使っています．桁あふれが心配なので，Int64 を使いました．

import Data.Int (Int64)

findCand :: Integral a => a -> a -> Maybe (a, a, a)
findCand n y
    | null cands = Nothing
    | otherwise = Just $ head cands
    where
        y0 = div y 1000
        cands = [(a, b, c) | a <- [0 .. n], b <- [0 .. n],
                             let c = n - a - b, c >= 0,
                             10 * a + 5 * b + c == y0]

main :: IO ()
main = do
    [n, y] <- fmap read . words <$> getLine :: IO [Int64]
    let res = case findCand n y of
                Just (a, b, c) -> [a, b, c]
                Nothing -> [-1, -1, -1]
    putStrLn $ unwords $ fmap show res

D - Katana Thrower

刀振り $a_1, a_2, \cdots, a_N$ はそれぞれ何度でも．刀投げ $b_1, b_2, \cdots, b_N$ は 1 回ずつ使えると考えれば，「刀を失う」という概念に頭を悩ませなくて済みます *4．ここで， $a_1, a_2, \cdots, a_N$ のうち最大のものを $m$ とし， $a_1, a_2, \cdots, a_N$ および $b_1, b_2, \cdots, b_N$ から $m$ 以上のものをとって降順に並べて得られる数列を $c_1, c_2, \cdots, c_M$ とします *5．そうすると，まずは $c_1, c_2, \cdots, c_M$ を順番に 1 回ずつ使って攻撃していき（段階 1），それらを使い果たしてもなおダメージの合計が $H$ に足りなければ，あとは足りるまで $m$ で繰り返し攻撃する（段階 2）のが，最善の戦略になります *6．実装では，この最善の戦略を再帰関数により表現しています．

import Data.Int (Int64)
import Data.List (sortBy, transpose)

divCeil :: Integral a => a -> a -> a
divCeil a b = (a + b - 1) `div` b

solve :: Integral a => a -> [a] -> [a] -> a
solve h as bs = f 1 h fs
    where
        a = maximum as
        fs = takeWhile (>= a) $ sortBy (flip compare) $ as ++ bs
        f i s [] = i - 1 + divCeil s a
        f i s (x : xs) = if s - x <= 0 then i else f (i + 1) (s - x) xs

main :: IO ()
main = do
    [_, h] <- fmap read . words <$> getLine :: IO [Int64]
    [xs, ys] <- transpose . fmap (fmap read . words) . lines <$> getContents
    print $ solve h xs ys

感想

なかなか時間が取れませんが，なるべくコンテスト後は復習し，その結果を何らかの文章に残したいものです．今回の問題は Haskell と相性が良かったのか，単純に私の知っている書き方でたまたま対応できただけなのか，D 問題まで Haskell で解けました．

*1:AtCoder Beginner Contest で安定して全完できないのに，上級者の方の猿真似をして無理やりいろいろな言語を使ったのも大きく響きました．

*2:本来は C++ や Python など多くのプログラミングコンテストのサイトで使える言語で復習すべきかもしれません．

*3:ただし，簡単のため第 2 式の両辺を 1/1000 倍しています．

*4:コンテスト中はこれがうまくできず，妙な DP を考えて撃沈しました．

*5:この新しい数列には，必ずしも全ての $b_i$ が含まれるとは限りません．すなわち，投げない刀が存在することがあります．

*6:このあたりは，コンテスト後の Twitter のタイムラインや，公式の解説を参考にしたうえで，いろいろ実験して確かめました．