Competitive Programming Advent Calendar 2015 五日目の記事です。

Beginner Contest レベルなら、呪文みたいな大量のコード (レギュラーコンテストに出てる人たちのコードはすごい) を書かないでも、意外とシンプルに書けることが多くて、パズル感覚で楽しめます。

Haskell で ABC をやる上で僕が感じた楽しいところ、楽しくないところをご紹介します。

楽しいところ

1. 関数が豊富

abc029.contest.atcoder.jp

import Control.Monad

main = do
  n <- readLn
  putStr . unlines . replicateM n $ "abc"

重複ありの組み合わせは replicateM 関数で作れるので、このようにびっくりするほど短く解けます。

他にもリストの基本操作 (sort, map, ...) から、置換や複数行文字列との相互変換まで、一通りの関数がそろっています。

http://hackage.haskell.org/package/base-4.8.1.0/docs/Data-List.html

replicateM は Control.Monad モジュールで定義された関数です。

http://hackage.haskell.org/package/base-4.8.1.0/docs/Control-Monad.html#v:replicateM

2. 関数定義が軽い、再帰が軽い

abc030.contest.atcoder.jp

import Control.Applicative
import Control.Monad

solve x y as bs c = case as of
    (a:as)    -> solve y x (dropWhile (<x+a) bs) as (c+1)
    otherwise -> c `div` 2

main = do
    -- 入力
    [n, [x, y], as, bs] <- replicateM 4 $ map read . words <$> getLine
    print $ solve x y as bs 0

基底部を除くと実質

solve x y (a:as) bs c = solve y x (dropWhile (<x+a) bs) as (c+1)

これだけです。短い！

多少複雑な問題でも

リスト構造が汎用的なので工夫でなんとかなることも多い。（ここがパズル的でおもしろい）

abc026.contest.atcoder.jp

import Control.Applicative
import Data.List

solve bs n = val $ map (solve bs) $ elemIndices n bs where
    val [] = 1
    val bs = maximum bs + minimum bs + 1

main = do
    _  <- getLine
    bs <- map (pred . read) . lines <$> getContents
    print $ solve (-1:bs) 0

楽しくないところ

Haskell で ABC をやる上で僕が感じた、楽しいくないところ

IO が遅い

標準的な入力関数で String 型で読み込むと、重くて TLE しばしば。

仕方なく、おまじないを使います。

import qualified Data.ByteString.Char8 as BC
import Data.Maybe (fromJust)

readInts = map (fst . fromJust . BC.readInt) . BC.words <$> BC.getLine

参考: Wc - HaskellWiki

List の弱みが辛い

ランダムアクセスが O(N)
値がイミュータブル

一応 Map/IntMap, Array, Vector など使えば解決できるっぽいですが、僕はまだ自在に泳げるほど慣れていません。

いずれにしても破壊的代入は実装が嵩んで辛くなりそう。。慣れるのかな。

これらを使わないで解ける問題はやっぱり限られます。

List だけで自明に解けた問題

ABC 026 - 030 で、List だけを使う解法を見つけられた問題と、見つけられなかった問題。

コンテスト	A	B	C	D
ABC023	o	o	x	o
ABC024	o	o	o	o
ABC025	o	o	o	x
ABC026	o	o	o	o
ABC027	o	o	o	o
ABC028	o	o	o	o
ABC029	o	o	o	o
ABC030	o	o	o	x

たま〜に、List だけでは素直に解けない気がする問題があります。解けない問題のほとんどは Map/IntMap でなんとかなって、ごく一部が Array/Vector まで要求される感じです。

Map/IntMap はそこまで怖くないので、積極的に使ったら良いかもしれないです。

余談

余談ですが最近、会社の人達と集まって AtCoder Beginner Contest をやっています。

f:id:na_o_s:20151206122304p:plain

初心者の方もいるので、経験者は得意言語を使わない縛りみたいな、僕は Haskell 縛りをしていたわけです。

競技プログラミングの布教活動のつもりだったけど意外に楽しんでもらえていて、だんだんみんな強くなってくるし、良いですよ。

na_o_ysのブログ

プログラミングなど

Haskell で始める AtCoder Beginner Contest