AtCoder に登録したら解くべき精選過去問 10 問を Haskell で解いてみた

#はじめに

AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ で紹介されていた10問をHaskellで解きました。他の人の記事(Rust, Python, C#, Java, Kotlin) も参考にした 6番煎じ （この記事を書いている途中にJavaScriptも出たので）7番煎じとなっております。
AtCoder Beginners Selection コンテストページ

対象

言語の解説を多めに入れていきますので、あまりHaskellに詳しくない人でもなんとか追えるかと思います。（その分とても長くなっているが）
「すごいHaskellたのしく学ぼう!」とか読み終えている人なら余裕で追えると思います（し、0問目とかの長ったらしい解説は飛ばして大丈夫だと思います）。

入出力 & 0問目 PracticeA はじめてのあっとこーだー（Welcome to AtCoder）

Rust の記事に

どの言語でも最初に躓くのが入力だと思います。

と書いてありますが、Haskellは特に入出力が難しいイメージを持たれている気がするので、解説していきます¹。とはいえ、具体的なコードがないのも分かりにくいと思いますので、0問目も同時に解説していきましょう。

main = do
 a <- readLn
 [b,c] <- map read . words <$> getLine
 s <- getLine
 putStrLn $ unwords [show (a + b + c), s]

（注: 「すごいHaskell」読み終わってる人はreadLnの解説だけ読めば十分です。簡単にいうとreadとgetLineを合わせた感じの関数です。²）

---

main はI/Oアクション（入出力にまつわる命令書）です。この do と <- を使った構文で複数のI/Oアクションをまとめ、単一のI/Oアクションにすることができます。³以下、それぞれの行が何をやっているのか解説していきます。

まず、4行目のgetLineから。これは、入力を1行取って入力された文字列を生成するI/Oアクションです。それをsに<-してやることで、sには入力された文字列が入ります。

次に、1行目のreadLnですが、これはgetLineして得られた文字列を解釈（例えば、文字列が"4"なら数値の4を、文字列が"[1,2,3,4]"だったらリスト[1,2,3,4]を）してくれるI/Oアクションです。数値を返すこともリストを返すこともできる関数なので、「どの型で解釈してほしいのか」を何らかの形で教えてあげないといけませんが、今回はreadLnした結果のaが5行目で+されているので、Haskellは無事に型を推論してやることができます⁴。（推論できない場合に失敗する、という話も後で言及します。）

---

さて、難関⁵は2行目のmap read . words <$> getLineです。順を追って解説していきましょう。
まず、map read . wordsはmap readとwordsを関数合成した関数（つまり、(map read . words) x == map read (words x)）です。wordsは文字列を空白で区切ってくれる関数なので、例えば

words "1 2 3 4" == ["1","2","3","4"]
words "alpha beta    gamma" == ["alpha","beta","gamma"]

です。
readは、先程言及したreadLnと似た感じで文字列を解釈してくれる関数なので、それをmapという関数でリストの各要素に適用してやることで

map read (words "1 2 3 4") == [1,2,3,4]

となるので、結果として map read . words は「スペース区切りされた数が書かれた文字列を、数値のリストにしてくれる」関数⁶ということになります。

さて、最後に<$>ですが、これの詳細な解説⁷はここではしません。

do
 hoge <- action
 let a = f hoge
 ...

というコード（let a = f hogeは、単にf hogeという値にaという名前をつけるという意味）を、

do
 a <- f <$> action
 ...

と書けるようにするおまじないだと思ってください。⁸

まとめると、map read . words <$> getLineは、「スペース区切りされた数が書かれた入力を1行受け取って数値のリストを生成するI/Oアクション」という、競プロでとても便利な定型句となります。以下の解説でも多用します。

---

最後に、putStrLn $ unwords [show (a + b + c), s] です。putStrLn hogeは定数hogeに入っている文字列を出力して改行するI/Oアクションです。unwordsはwordsの逆の役割をする⁹関数で、

unwords ["a","b"] == "a b"

のように、文字列のリストをスペース区切りの文字列にまとめてくれます。（ちなみに、スペースが要らないときにはconcatという関数が使えます。）

showはreadの逆の役割をする関数¹⁰で、ここでは数値a + b + cを文字列に変換してくれます。sは元から文字列なので変換してはいけません。

$は、(foo bar)(hoge baz)をfoo bar $ hoge bazと書けるようにするおまじないだと思っておけばそんなに問題ないでしょう¹¹。なお、右結合なので、a b $ c d $ e fと書いてあったら(a b)(c d $ e f)なので(a b)((c d) (e f))です。

---

以上で0問目の解説は終わりです。長い説明にお付き合い下さりありがとうございます。もうちょっとだけ続くんじゃ。

1問目 ABC086A Product

main = do
 [a,b] <- map read . words <$> getLine
 if (a * b) `mod` 2 == 0 then putStrLn "Even" else putStrLn "Odd"

2行目で先程解説したコードを使ってaとbを読み込み、それの積の剰余で条件分岐をしています。剰余を取る関数にはmodとremの2つがあり、負の数での挙動が違います。

(-6) `mod` 5 == 4

(-6) `rem` 5 == (-1)

大抵の場合はmodを使っておけば問題ないでしょう。なお、商を求める関数にも同様にdivとquotがあります。divと組になるのがmodで、quotと組になるのがremです。
とはいえ、quotとremは私は未だに使ったことがないですし、実用上もdivとmodを覚えておけば十分でしょう。

ちなみに、最後の行は

 putStrLn $ if (a * b) `mod` 2 == 0 then "Even" else "Odd"

とも書けます。この場合、$が無いと構文エラーになるので気をつけましょう。

#2問目 ABC081A Placing Marbles

main = getLine >>= print . length . filter (=='1')

無駄に簡潔に書いているので解説が面倒ですが、面倒臭がっていても始まらないのでちゃんと解説していきます¹²。

---

まず、print . length . filter (=='1')から見ていきましょう。恒例のごとく、これはprint と length と filter (=='1')を関数合成したものです。

第一引数に条件を指定し、第二引数にリストを指定することで、リストの中から条件を満たす値だけを抜き出せる関数がfilter です。(=='1')は「文字 '1'と等しい」という条件を表すこと¹³、Haskellで文字列は文字のリストであることを考慮すると、

filter (=='1') "1foo2bar1hoge31415" == "1111"

というように、filter (=='1')は「文字列から文字'1'のみを抜き出す関数」となることがわかります。

これに、リストの長さを返す関数である length を合成してやることで、「文字列から文字'1'のみを抜き出し、その長さを数える」＝「文字列の中に'1'が何個あるか数える」関数が出来上がります。

length (filter (=='1') "1foo2bar1hoge31415") == 4
(length . filter (=='1')) "1foo2bar1hoge31415" == 4

最後に合成されているprintという関数は、showしたものをputStrLnする関数です¹⁴ので、結果として、print . length . filter (=='1')は「文字列を受け取って、その中の文字'1'の個数を出力する命令書を作る」という関数になることが分かります。

---

さて、最後に>>=を見ていきましょう。>>=というのは、 m >>= f が

do
 a <- m
 f a

と等価になるような演算子です¹⁵。今回の場合は、getLineが生成した文字列を先程説明した関数print . length . filter (=='1')に渡す役割を担っていることが分かります。

#3問目 ABC081B Shift only

最初に解いた時に私の提出したコードは

import Data.Maybe
main = do
 _ <- getLine
 a_s <- map read . words <$> getLine
 let divisor = foldr1 gcd a_s
 print . subtract 1 . length . takeWhile isJust . iterate (>>=f) $ Just divisor

f x
 | x `mod` 2 == 0 = Just(x `div` 2)
 | otherwise = Nothing

なのですが、解法が微妙で、かつあまりにも解説に向かない¹⁶ので、解説にはIamnoob様（Twitter, AtCoder）のコードを元にして私が少々手を加えた、↓のコードで解説していきたいと思います。

f x = if x `mod` 2 == 0 then 1 + f (x `div` 2) else 0

main = do
 getLine
 a <- map read . words <$> getLine
 print $ minimum $ map f a

---

まずはmainを読んでいきましょう。
最初にgetLineをしていますが、その結果生成される文字列を使わずに捨てています。ここには入力される正の整数の個数が書いてあるのですが、map read . words <$> getLineを使って一行全部読んでいる現状ではその情報は必要ないからです。
なお、ここでgetLineの代わりにn <- readLnと書くと、

error:
      Ambiguous type variable ‘a0’ arising from a use of ‘readLn’
      prevents the constraint ‘(Read a0)’ from being solved.
      Probable fix: use a type annotation to specify what ‘a0’ should be.

というエラーが出ます。第0問と異なり、nはプログラムの残りの部分で使われていないので、「どの型に変換すればいいのか分からない」と怒られてしまいます。「使われないなら逆にどの型でもいいじゃん」と思われるかもしれませんが、そうもいかないのです。

map read . words <$> getLineで得た $A_1$ ~ $A_n$ のリストaに、「2で何回割れるかを数える」関数f（後で解説します）をmapすることで、aの各要素にfが適用されたリストが手に入ります。そのリストの最小値をminimum関数を使って求めてやることで、答えを求められます。

---

後は、「2で何回割れるかを数える」関数fを読み解いてやれば終了です。長々と説明してもいいですが、具体的な数で挙動を追いかけてみましょう。

f 24
if 24 `mod` 2 == 0 then 1 + f (24 `div` 2) else 0 -- fの定義
1 + f (24 `div` 2)  -- 24 `mod` 2 == 0 は真
1 + f 12  -- 24 `div` 2を計算
1 + (if 12 `mod` 2 == 0 then 1 + f (12 `div` 2) else 0) -- fの定義
1 + (1 + f (12 `div` 2) ) -- 12 `mod` 2 == 0 は真
1 + (1 + f 6) -- 12 `div` 2を計算
1 + (1 + (if 6 `mod` 2 == 0 then 1 + f (6 `div` 2) else 0)) -- fの定義
1 + (1 + (1 + f (6 `div` 2))) -- 6 `mod` 2 == 0 は真
1 + (1 + (1 + f 3)) -- 6 `div` 2を計算
1 + (1 + (1 + (if 3 `mod` 2 == 0 then 1 + f (3 `div` 2) else 0))) -- fの定義
1 + (1 + (1 + (0))) -- 3 `mod` 2 == 0 は ††偽††
3 -- 計算

要するに、命令型言語ならループで書くような挙動を、fの定義の中でfを使うことで実現するわけです。これを「再帰」と言います。

#4問目 ABC087B Coins

main = do
 a <- readLn
 b <- readLn
 c <- readLn
 x <- readLn
 print $ length [() | u <- [0..a], v <- [0..b], w <- [0..c], 500*u+100*v+50*w == x]

2〜5行目でa,b,c,xを読んだあと、6行目で全探索をしています。
命令型言語だったら3重ループを書くところですが、Haskellでやる場合は「リスト内包表記」という構文を上手く使うのが便利です。

[ ~ ]の部分がリスト内包表記です。「リスト内包表記」というもの自体は、Pythonなどで目にしたり耳にしたりしたことのある方もいるのではないでしょうか¹⁷。

やっていることは簡単です。まず、|の右側を見てみましょう。[0..a]で0からaまでの整数のリストを作ることができ、そこからuを取り出しています。同様にvとwを取り出した後、500*u+100*v+50*w == xの条件を満たす候補だけを残しています。
|の左側では、例えば(u,v,w)と書いてやることで、全体としては条件を満たす3つ組だけが入ったリストが出来上がりますが、今回は具体的な値には興味がないため、空タプル（0要素からなるタプル）()を置いています。

リスト内包表記でリストが出来上がったら、それのlengthをprintしてやれば完了です。

#5問目 ABC083B Some Sums

main = do
 [n, a, b] <- map read . words <$> getLine
 print $ sum [k | k <- [1..n], evaluate k >= a, evaluate k <= b]

evaluate k = sum [read [c] | c <- show k]

2行目はテンプレですね。3行目にはリスト内包表記があります。「1からnまでの整数を取ってきて、それをevaluateという関数（桁の総和を計算する関数。後述する）に入れたものがa以上でありb以下であるもの」が[ ~ ]で表されるリストなので、それの総和をsumという関数で取って、printしているだけです。

次に、evaluateですが、これは前述の通り桁の総和を計算する関数です。これもまたリスト内包表記とsumの組み合わせですね。ちょっと分かりにくいので、具体的にevaluate 1234がどんな値になるか見てみましょう。

evaluate 1234
sum [read [c] | c <- show 1234] -- 定義で置き換え
sum [read [c] | c <- "1234"] -- showは数値を文字列に変換してくれる
sum [read [c] | c <- ['1', '2', '3', '4'] ] -- 文字列は文字のリスト
sum [read ['1'], read ['2'], read ['3'], read ['4']] -- リスト内包表記を展開
sum [read "1", read "2", read "3", read "4"] -- 文字のリストは文字列
sum [1, 2, 3, 4] -- readは文字列を数値に変換してくれる
10 -- sumは総和

というわけで、桁数の総和が計算できることがわかりました¹⁸。

#6問目 ABC088B Card Game for Two

最初に解いた時に私の提出したコードは

import Data.List
main = do
 _ <- getLine
 a_s <- map read . words <$> getLine
 print $ analyze $ reverse $ sort a_s

analyze :: [Integer] -> Integer
analyze = f . unzip . chop
f(us,vs) = sum us - sum vs

chop (a:b:c) = (a,b) : chop c
chop [a] = [(a,0)]
chop [] = []

なのですが、長いのでcojna様（Twitter, AtCoder）のコードを参考にした以下のコード

import Data.List
main = do
 getLine
 a_s <- map read . words <$> getLine
 print $ sum $ zipWith (*) (cycle [1, -1]) $ reverse $ sort a_s

で解説します。

リストをソートする必要があるので、先頭でimport Data.Listという宣言をしてsort関数を使えるようにします。

入力の1行目を単独getLineで読み飛ばし、$a_1$ ~ $a_n$の入ったリストa_sをmap read . words <$> getLineで入手しています。

5行目では、まずreverse $ sort a_sで、a_sをsortでソートした後reverseで逆順にしたリストを作っています。これにより、降順でソートされます。

あとは、これを先頭からそれぞれAliceとBobに振り分けていけばいいのですが、(Aliceのカードの総和) - (Bobのカードの総和)が求まればよいので、奇数番目の要素を1倍し、偶数番目の要素を-1倍して総和を取ればよいことになります¹⁹。それを行っているのがその次のzipWith (*) (cycle [1,-1])とsumです。
まず、cycle [1, -1]は1と-1が交互に出てくる無限リスト[1, -1, 1, -1, 1, -1, ...]を生み出します²⁰。zipWith関数は、次のような挙動をする関数です。

zipWith f [a1, a2, ...., an] [b1, b2, ...., bm]
== [f a1 b1, f a2 b2, ..., f am bm]

（ただし、$n \ge m$とする）

二つのリストを先頭から、ジッパーで閉じるようにfで一つずつ対応させて新たなリストを作るのがzipWith関数です。リストの長さが異なるときには短い方のリストの長さになるので、無限リストと有限リストをzipWithしてできる新しいリストの長さは有限です。

ということで、2つのリストを(*)でzipWithしてsumを取ったものをprintすることで、答えが出ます。

#7問目 ABC085B Kagami Mochi

import Control.Monad
import Data.List
main = do
 n <- readLn
 ds <- replicateM n readLn
 print $ length $ group $ sort (ds :: [Integer])

replicateM k mは、I/Oアクションmをk回行い、それぞれの結果をまとめたリストを結果とするI/Oアクションです。replicateMはControl.Monadに定義されているので、予めimportしておきましょう。

これをsortしてやるのですが、その際にdsが整数のリストであるという情報も提供しておきましょう。そのための記述が :: [Integer]で、これがないと型推論が失敗します。

次に、groupという関数を使います。これは公式に載っている例が分かりやすいので引用すると、

group "Mississippi" = ["M","i","ss","i","ss","i","pp","i"]

というように、隣り合っている同一の値をグループ化してくれます。

これのlengthをprintすれば完了です。

#8問目 ABC085C Otoshidama
私のコード（↓）は実行速度が比較的早い(1msだった)のですが、長いので解説には用いず、

main = do
 [n, y] <- map read . words <$> getLine
 let u = y `div` 1000 - n
 case analyze u of
  Nothing -> putStrLn "-1 -1 -1"
  Just (a,b) -> putStrLn $ 
   if n-a-b < 0 then "-1 -1 -1" else unwords $ map show [a,b,n-a-b]

analyze :: Integer -> Maybe(Integer,Integer)
analyze u
 | u < 0 = Nothing
 | u >= 36 = let (a_,b_) = head $ foo $ (u `mod` 36)+36 in Just((u `div` 36 - 1)*4+a_,b_)
 | otherwise = case foo u of
  [] -> Nothing
  k:_ -> Just k

foo u = [(a,b) | a <- [0..7], b <- [0..8], 9*a+4*b == u]

これまたIamnoob様のコードで解説させていただきます。

main = do
 [n, y] <- map read . words <$> getLine
 let ans = [[a, b, c] | a <- [0 .. n], b <- [0 .. (n - a)], let c = n - a - b, 10000 * a + 5000 * b + 1000 * c == y]
 putStrLn $ unwords $ map show $ if null ans then [-1, -1, -1] else head ans

3行目はリスト内包表記で全探索をしていますが、$a+b+c=n$ かつ $c\ge0$ なので $n-a\ge b$ が必要になります。そのため、aの範囲は[0 .. n]ですがbの範囲は[0 .. (n - a)]にする必要があります。あとは10000 * a + 5000 * b + 1000 * c == yの条件を加えてやるだけです。
そうして得られた、条件を満たす[a,b,c]を集めたリストにansという名前を付けています。

最後の行については、

• null: 空リストならTrue、それ以外はFalseを返す関数
• head: リストの先頭要素を返す関数

を解説すれば十分でしょう。

#9問目 ABC049C 白昼夢 / Daydream

main = do
 s <- getLine
 putStrLn $ if analyze (reverse s) then "YES" else "NO"

analyze "" = True
analyze ('m':'a':'e':'r':'d':k) = analyze k
analyze ('r':'e':'m':'a':'e':'r':'d':k) = analyze k
analyze ('e':'s':'a':'r':'e':k) = analyze k
analyze ('r':'e':'s':'a':'r':'e':k) = analyze k
analyze _ = False

先頭から処理していくと厄介なので、一旦reverseしてから後ろから処理していっています。
'm':'a':'e':'r':'d':kはmaerdで始まる文字列にマッチし、残りの部分にkという名前がつくので、そのkを再びanalyzeにかける、ということをやっていって、最終的に空文字列が得られたらTrue、そうでなければFalseです。

あとは、それに応じて"YES"か"NO"を返し、putStrLnしてやれば完了です。

#10問目 ABC086C Traveling

import Control.Monad
main = do
 n <- readLn
 txys <- replicateM n $ map read . words <$> getLine
 putStrLn $ if analyze ([0,0,0]:txys) then "Yes" else "No"

analyze [a,b] = reachable a b
analyze (a:b:xs) = reachable a b && analyze (b:xs)

reachable [t1,x1,y1] [t2,x2,y2] = 
 (dt >= dx + dy) && ( (dt - dx - dy) `mod` 2 == 0)
 where dx = abs(x2-x1); dy = abs(y2-y1); dt = t2-t1

入力を読み取ったら、それの先頭に[0,0,0]²¹を付けて、analyzeに渡します。
analyzeでは、再帰を使って、「隣り合うt,x,yの組にreachable関数を適用し、全部がTrueならTrue」という処理を書いています。「移動が毎回成功するなら、全体でも成功する」ということですね。

最後にreachableですが、whereという予約語を使って計算途中の値に名前を付けています。

#おわりに
解説を書くのが予想以上に面倒でしたが、お役に立てれば幸いです。
定数倍が厳しくない問題・実装速度が実行速度より重視される系の問題ではHaskellは普通に有用なので、おすすめです（Haskellはいいぞ）

#脚注

1. 初学者の混乱を防ぐためにも、用語とかはなるべく「すごいHaskell」に合わせるようにして解説していきます。 ↩

2. 厳密に言うと、readではなくreadIOです。 ↩

3. 詳しくは「Haskell モナド」とか「Haskell 入出力」とかで調べるか、「すごいHaskell」の第8章を読みましょう。 ↩

4. 「整数型も小数型も+できるのに、なんでコンパイルが通るの？」と気づいた人はとてもすごいです。この場合、コンパイラが気を効かせて「Integerでよさそう」としてくれるのでコンパイルが通ります。-Wallを付けてコンパイルすると、Defaulting the following constraints to type ‘Integer’というメッセージが(ghcなら)出て、このことを教えてくれます。 ↩

5. これがスラスラ読めるプロは温かく見守っていただけると幸いです。 ↩

6. 「型制約がついていないんだから、数値とは限らんぞ」はい、そのとおりです。 ↩

7. 型クラスFunctorのメソッドfmapの別名 ↩

8. 言い訳をするなら、instance Functor IO は fmap f x = x >>= (pure . f) と定義されていて、かつIOモナドがモナド則を満たしている（のでpureしたものを<-したら元の値になる）以上、そんなに誤った説明でもない気がします。（不十分な説明であることは確かだが） ↩

9. unwords (words "a b") == "a b"なので、逆関数ではありません。 ↩

10. これもまたshow(read "[1, 2]" :: [Int]) == "[1,2]"なので、逆関数ではありません。 ↩

11. foo bar(hoge baz)、と説明されることが多い気がしますが、その理解だとproduct $ map (+1) [1,2,3]に1を足したい時に1 + product $ map (+1) [1,2,3]と書いてしまって（これは1 + product (map (+1) [1,2,3]) ではなく (1 + product) (map (+1) [1,2,3])なのでダメ）エラーが出るので、第一項にもカッコを付けて教えています。 ↩

12. こうやって簡潔に書けるのもHaskell競プロの利点なので、解説用にわざわざ書き直さずにあえてこのまま解説します。 ↩

13. この記法は「セクション」と言います。頻出するので、「すごいHaskell」とかを読んでちゃんと理解しておきましょう。 ↩

14. 公式のソースコード を見てみると一発でわかりますね。 ↩

15. もちろん、本当はdoが>>=に翻訳されているわけなので、「等価」という表現で逃げています。 ↩

16. 腕に自信のあるプロは是非解読してみましょう。 ↩

17. ちなみに、Pythonのリスト内包表記はHaskellに直接由来するそうです。 ↩

18. import Data.CharしてdigitToIntしてもいいんですが、「showとreadが対称的」「Preludeに入っていない関数を暗記させるのもなんかなぁ（後でreplicateMとかsortとか出てくるけど）、そもそも最初に組んだときは私がdigitToIntの存在を知らなかったし」「説明する関数の数が少なければ少ないほど執筆が楽」ということもあり、今回はreadを使いました。ちなみに最初に組んだときはsubtract (fromEnum '0') . fromEnumとか書いてました。 ↩

19. ちなみに、私はこの発想が思いつかなかったので、上記のコードではかなり面倒なことをしています。 ↩

20. Haskellでは無限の長さを持つリストを扱うことができます。もちろん、長さを求めようとしたりソートしようとしたりすると無限ループが発生します。ここで使ったように、zip系の関数などと合わせて使うのが定石です。 ↩

21. tとxとyの組を表すにはタプルを使ったほうが健全で、私も最初の提出ではタプルを使っていましたが、コードが長くなるのでこのコードでは全部リストで処理しています。 ↩