はじめに

久しぶりに Haskell を書きたい & 久しぶりに競技プログラミングの問題を解きたいと思い、解こうとしたら久しぶりすぎていろいろ忘れていたので、思い出すついでに記事を書いてみました。

この記事では、Haskell で競技プログラミングの問題を解く際に役立つ、入力を受け取るパターンをいくつか紹介します。（久しぶりすぎて古い書き方かもしれないです。新しい書き方を知っていたらぜひコメント等で教えてください！）

Haskellで標準入力を受け取る

AtCoder など、競技プログラミングでは標準入力から与えられた入力を処理して、答えを標準出力に出力する、といった形式が多いです。

Haskell における入出力は IO モナドに包まれているので、初心者がきちんと理解したうえで使えるようになるまでに時間がかかります。ですが、競技プログラミングでは入力のパターンはそれほど多くないので、この記事で紹介するパターンの組み合わせで大抵なんとかなると思います。

1行の入力を受け取るパターンと、複数行の入力を一度に受け取るパターンをそれぞれ紹介します。

1行の入力を受け取る

1つの文字列

文字列 $S$ が与えられます。

$S$

例: A - Past ABCs

例

ABC349

main = do
  s <- getLine

getLine は入力を1行受け取ります。

1つの数値

数値 $N$ が与えられます。

$N$

例: A - Penalty Kick

例

main = do
  n <- readLn :: IO Int

readLn は入力を1行受け取り、適切な型に変換してくれます。

1行に複数の文字列

複数の文字列 $S_n$ が与えられます。

$S_1\ S_2\ S_2\ ...\ S_N$

例

abc def ghi

main = do
  ss <- words <$> getLine

getLine で1行取得したあと、words で単語ごとに分けます。

1行に複数の数値

複数の文字列 $A_n$ が与えられます。

$A_1\ A_2\ A_3\ ...\ A_N$

例: F - Double Sum

例

2 5 3

main = do
  as <- map read . words <$> getLine :: IO [Int]

getLine で1行取得して、words でスペース区切りで分割したあと、 map read でそれぞれ数値に変換します。

以下のように1行に含まれる数値の数が固定の場合は、パターンマッチでそれぞれの変数に束縛するのがオススメです。

$i\ j$

main = do
  [i, j] <- map read . words <$> getLine :: IO [Int]

複数行の入力を受け取る

各行1つの文字列

整数 $N$ と文字列が $N$ 行与えられます。

$N$
$S_1$
$S_2$
$S_3$
$\vdots$
$S_N$

例: A - Majority

例

3
For
Against
For

import Control.Monad

main = do
  n <- readLn
  ss <- replicateM n getLine

Control.Monad の replicateM を使うと getLine 等のIOアクションを複数回行うことができます。

以下のように getContents で終端まで取得して、lines で改行で分割する方法もあります。

main = do
  _ <- getLine
  ss <- lines <$> getContents

各行1つの文字列

整数 $N$ と $N$ 個の数値 $A_N$ が複数行で与えられます。

$N$
$A_1$
$A_2$
$A_3$
$\vdots$
$A_N$

例: F - Product Equality

例

先程の例の getLine を readLn に変更するだけです。

import Control.Monad

main = do
  n <- readLn
  ss <- replicateM n readLn :: IO [Int]

getContents で取得した後 read で文字列から変換することもできます。

main = do
  _ <- getLine
  ss <- map read . lines <$> getContents :: IO [Int]

1行に複数の値

$H\ W$
$S_{1,1}\ S_{1,2}\ \dots\ S_{1,W}$
$S_{2,1}\ S_{2,2}\ \dots\ S_{2,W}$
$S_{3,1}\ S_{3,2}\ \dots\ S_{3,W}$
$\vdots$
$S_{H,1}\ S_{H,2}\ \dots\ S_{H,W}$

例: F - Rotation Puzzle

例

import Control.Monad

main = do
  [h,_] <- map read . words <$> getLine
  sss <- replicateM h $ map read . words <$> getLine :: IO [[Int]]

1行に複数ある場合のパターンを、 replicateM で繰り返すだけです。

また、以下のように座標が与えられ、タプルのリスト [(Int, Int)] として受け取りたい場合もあります。

$N$
$X_1 \ Y_1$
$X_2 \ Y_2$
$X_3 \ Y_3$
$\vdots$
$X_N \ Y_N$

その場合は以下のように、1行ごとにタプルを作るとタプルのリストとして扱えます。

import Control.Monad

main = do
  n <- readLn
  xys <- replicateM n $ do
    [x,y] <- map read . words <$> getLine
    return (x,y) :: IO (Int,Int)

おまけ

今回この記事を書いたきっかけは、冒頭も書きましたが久しぶりに Haskell を書きたい & 久しぶりに競技プログラミングの問題を解きたいと思ったからです。

久しぶりに問題を解いてみて「やっぱり Haskell を書くのは楽しい！」と思いました。
実際に解いた問題の一つが以下の問題です。

僕が投稿した回答はこちらです。

回答の一部がこちらになります。
これは、入力(第2引数) の先頭から、列(第1引数)に対してルールに従って追加していく関数 f です。

f :: [Int] -> [Int] -> [Int]
f xs []     = xs       -- 入力が空になったら終了
f [] (y:ys) = f [y] ys -- 列が空の時は入力の先頭(y)を列に入れる
f (x:xs) (y:ys)
  | x == y    = f xs (y+1:ys) -- 列と入力の先頭が同じ場合は列の先頭(x)を除いて、入力の先頭(y)を+1
  | otherwise = f (y:x:xs) ys -- そうでない場合は入力の先頭(y)を列に追加

型定義を除いた実装部分はわずか5行です。

Haskell で競技プログラミングの問題を解こうとすると、今回紹介したように入出力などが難しい点が多いため、他の言語を使いたくなる気持ちもありますが、上記のようにパターンマッチや再帰の書きやすいので、 Haskell もおすすめです。

Haskellで競技プログラミング～入力編～

はじめに

Haskellで標準入力を受け取る

1行の入力を受け取る

1つの文字列

1つの数値

1行に複数の文字列

1行に複数の数値

複数行の入力を受け取る

各行1つの文字列

各行1つの文字列

1行に複数の値

おまけ