Haskellで競技プログラミング IO編

_この記事は2013年の情報オリンピック夏季セミナーの発表のために

動機

Haskellには競技プログラミングに使えるCoolな機能が沢山あります。
パターンマッチやプレースホルダ、パターンガード、柔軟な関数合成などです。

下はAtCoder Regular Contest #14のB問題に対する回答です。
再帰や場合分けがかなりシンプルに書けます。

ARC14B

import Control.Monad
import Control.Applicative
import Data.List
 
main :: IO ()
main = do
  n <- readLn
  (w:ws) <- replicateM n getLine
  putStrLn $ case check [w] ws True of
    Nothing -> "DRAW"
    Just True -> "WIN"
    Just False -> "LOSE"
 
check _ [] _ = Nothing
check dict@(la:_) (w:ws) b
  | last la /= head w = Just b
  | w `elem` dict = Just b
  | otherwise = check (w:dict) ws (not b)

このコードを見た人は早速Haskellで問題を解いてみたくなってしまうに違いありません。
そして書き始めたとき、ある問題に気づきます。

『入力の受け取り方が分からない(^_^;)』

名著『すごいHaskell楽しく学ぼう』でも入力が出来るようになるのは全15章中の8章とかなり後ろの方です。

これには勿論理由があり、Haskellの素ん晴らしい性質の一つである__参照透過性__と、IOによる副作用を共存させる仕組みとしてモナドというものが用いられますが、こいつがそれなりにややこしく理解に時間が掛かるからなのです。

競技プログラミングに使う分にはモナドを理解する必要は全くなく、いくつかある入力の方法を覚えてしまえばそれで終わりなので、この記事ではそのような方法を紹介したいと思います。

do記法

まずHaskellでの対話環境であるghciを起動して行入力関数であるgetLine関数の型を調べてみましょう。

ghci> :t getLine -- :t はgetLineの型を返す。
getLine :: IO String -- getLineの型は「IO String」である。

これはIO String型であってString型ではないのでString型を取る関数にこれを渡しても型エラーが出てしまいます。do記法を使うことでIO String型からStringを取り出すことができます。

do記法による入力

main = do
  進捗 <- getLine -- input: 進捗
  putStrLn (進捗 ++ "ダメです！") -- output: 進捗ダメです！

一行に空白区切りの複数の入力がある場合にはwords関数を用いて文字列の配列に変換出来ます。Haskellの関数合成は.を用いてfunc2 . func1と表すことが出来ますが、IOなどに包まれた型の中身をIOから取り出して関数を作用させた後またIOにしまうには<$>を用います。わかりにくいですが、IO StringのStringの部分だけに関数を適用し、またIO なんとかに戻すことが出来るということです。<$>とwordsを使うことでIO StringをIO [String]に変換出来ます。

空白区切りの入力

import Control.Applicative

main = do
  ss <- words <$> getLine -- input: hoge fuga piyo
  putStrLn (head ss) -- output: hoge

複数の数字が区切られている時

import Control.Applicative

main = do
  ss <- (map read . words) <$> getLine -- input: 123 456 789
-- ss = [123, 456, 789]
  putStrLn $ show $ foldl (+) 0 ss -- output: 1368

putStrLn $ show $ foldl (+) 0 ssというのは、foldlに(+)と0を部分適用した関数とshowという関数とputStrLnという関数を関数合成した関数にssという引数を与えるという意味です。

<-はパターンマッチを利用してリストの中身を個別の変数に束縛することが出来ます。

パターンマッチ

import Control.Applicative

main = do
  [a,b] <- words <$> getLine -- 空白区切り文字列の1番目と2番目をa,bに束縛する
  (c:cs) <- getLine -- 入力文字列の最初の文字と後ろの文字とそれに続く文字列をc,csに束縛する
  puts a  -- input: ちなつ あかり, output: ちなつ
  puts cs -- input: コモナド, output: モナド

パターンマッチに失敗すると実行時エラーが出るので一般的なプログラムを書くときは注意が必要です。競技プログラミングで入力フォーマットが保障されている時などは気にしなくてよいでしょう。

モナド型クラスメソッド

do記法は実はモナドの合成のための専用構文です。この専用構文を用いないと前述のコードは下のようになります。

>>=の型は以下のとおりで、getLine >>= putStrLn . funcはfuncに入力を渡して変換した文字列を出力できます。

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

普通の入力

main = getLine >>= putStrLn . (++ "ダメです！")
-- input: 進捗
-- output: 進捗ダメです！

区切られた入力

main = getLine >>= putStrLn . (unwords . map reverse) . words
-- input: hoge fuga piyo
-- output: egoh aguf oyip

複数の数字が区切られている時

main = getLine >>= putStrLn . solve . map read . words

solve :: [Int] -> String
solve = show . foldl (+) 0
-- input: 123 456 789
-- output: 1368

テンプレート

main = getLine >>= putStrLn . solve

solve :: String -> String

競技プログラミングの範囲だとdo記法よりも簡潔で綺麗になる場合が多いので、出来れば使えるようになりたいテクニックです。

便利関数

ghciの:tを使うと関数の型がわかります。関数の機能と使い方は型と名前からなんとなく推測してください。

putStr

文字列を末尾に改行を付加しないで出力します。

putChar

文字を末尾に改行を付加しないで出力します。

print

Showのインスタンス型を受け取りshowした結果を表示します。
（GHCiで実行した時表示される文字列になります。）

when

BoolとIOアクションを受け取り、Bool値がTrueの場合にIOアクションを実行します。

when

ghci Control.Monad> when (1 > 0) $ do putStrLn "Tlue"

interact

Stringを引数に取りStringを返す関数を渡すと、入力をその関数で変換した結果の文字列を出力してくれます。interactは終端文字が与えられるまで関数を繰り返しますが、遅延評価により入力文字列が必要になった時に入力を要求されます。

interact

main = interact $ unwords . map reverse . words

-- input: hoge fuga piyo
-- output: egoh aguf oyip

readLn

入力の型を推論します。

main = do
  n <- readLn -- input: 55
  putStrLn . show $ n * n -- output: 3025

getContents

終端文字までの全ての文字列（改行含む）を得られます。

getContents

main = do
  s <- getContents -- input: 1234\n5678\n90
  putStrLn . show . foldl (+) 0 . map read . lines $ s -- output: 7002

mapM_

リストの要素に対してIOアクションを実行できます。

mapM

ghci> mapM_ print [1, 2, 3]
1
2
3

replicateM

N行の入力を取るのに便利です。

replicateM

import Control.Monad
main = do
  s <- replicateM 3 getLine -- input: 123\n456\n789
-- s == ["123", "456", "789"]
  putStrLn . show . foldl (+) 0 . map read $ s -- output:1368

具体例

現在(2013/8/30)でHaskellが使えるオンラインコンテストジャッジはAtCoderとCodeforcesだけです。英語は読めないのでAtCoderの問題を使って入力を受け取ってみましょう。

ARC14A

1. 1行目にはたこ焼きの番号を表す整数 N(1≦N≦1000) が与えられる。

入力例

N

実装例

main = do
  n <- readLn
  putStrLn $ if even n then "Red" else "Blue"

ARC14B

1. 1行目には整数 N(1≦N≦100) が与えられる。
2. 2行目からN+1行までのN行では、文字列Wiが与えられる。

入力例

N
W_1
W_2
:
W_N

実装例

import Control.Monad
main = do
  n <- readLn
  ss <- repliciateM n getLine
  putStrLn $ solve n ss

solve :: Int -> [String] -> String
solve = undefined

ARC14D

1. 1行目には空白で区切られた整数all,N,Mが与えられる。
2. 2 行目からN+1行までのN行では整数Liが与えられる。
3. N+2行目からN+M+1行までのM行では整数xi,yiが与えられる。

入力例

all N M
L1
L2
:
LN
x1 y1
x2 y2
:
xM yM

実装例

import Control.Monad
import Control.Applicative

main = do
  [all,n,m] <- map read . words <$> getLine
  l <- replicateM n readLn
  xy <- map (map read . words) <$> replicateM m readLn
  
  putStrLn $ solve all l xy

solve :: Int -> [Int] -> [[Int]] -> [Int]
solve = undefined

まとめ

• Haskellは強い
• でもIOが難しい
• do記法が手続きっぽくて書きやすい
• モナドを使うとシンプルに書けて格好良い
• モナドが使えなくても入出力用の関数を使える場合がある
• 競技プログラマで使うようなパターンは限られているので覚えてしまおう