# AtCoder in Haskell

2020 年 1 月 12 日の [ABC151](https://atcoder.jp/contests/abc151)  から
Haskell で参加することにした（それまではC#で参加。AtCoder 自体の初参加は2019年
の[ABC137](https://atcoder.jp/users/unnohideyuki/history/share/abc137))

## ごく基本的なことがら

### Int のサイズ

組み込み型である Int のサイズ（表現可能な値の範囲）は環境依存だが、
AtCoder は 64-bit 環境であるらしく、基本的に整数型としては Int を使えばよい。

$$<pre>{
main = do
  print (maxBound::Int)
  print (minBound::Int)
$$}

↑これを、AtCoder の「コードテスト」で実行した結果が↓

$$<pre>{
9223372036854775807
-9223372036854775808 
$$}

## B
### Bellman-Ford の単一始点最短経路アルゴリズム
始点を固定したときに、
ほかのすべての頂点との最短路を求める最短経路問題を解くアルゴリズムのひとつ。
Dijkstra に比べ遅いが、閉路がある場合にも対応できる。

コード片：
[BellmanFord](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/BellmanFord.hs)

$$<pre>{
shortestPath :: Int -> V.Vector (Int, Int, Int) -> Int
  -> IO (Maybe (V.Vector Int))
shortestPath s edges numV = ...
$$}

このコードは、閉路がない場合には単一始点最短経路問題の答えを返し、
閉路があった場合には Nothing を返す。

終点も固定した、２頂点対最短経路問題にも使用できるが、
その場合、２頂点間の経路に関係のない箇所に閉路があっても差し支えないため、
上述のアルゴリズムそのままでなく、改造が必要となる。
（「２週目」にも更新があったノードの距離を Inf とする）

※改造せずにもちいて、２頂点間に関係ない閉路を検出してしまい
[WA](https://abc061.contest.atcoder.jp/submissions/12075753)

[ABC137E](https://atcoder.jp/contests/abc137/tasks/abc137_e) の入力例３も見よ。

使用例：

- [ABC061D - Score Attack](https://abc061.contest.atcoder.jp/submissions/12077234)
- [ABC137E -  Coins Respawn](https://atcoder.jp/contests/abc137/submissions/12077070)

### Binary Search (二分探索)

コード片： [snippets/bisect.hs](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/bisect.hs)

Python の bisect_right, bisect_left を一般化して、関数を引数にとる形にして移植。
整列済の配列などコレクションに対して使えるのはもちろん、AtCoder で頻出の判定関数を引数にとることもできる。

配列中に、検索対象と等しい値がひとつ以上あったときに、 BisectRight はそれらの一番右のものより、さらに右隣りのインデックスを返す。 BisectLeft は、それらの一番左のもののインデックスを返す。

配列中に、検索対象と等しい値がなかった場合には、検索対象よりも大きな要素のうち最小のもののインデックスを返す（Right/Left 共通）

使用例：

- [ABC146C - Buy an Integer](https://atcoder.jp/contests/abc146/submissions/8909979)
- [ABC056C - Go Home](https://atcoder.jp/contests/abc056/submissions/11627977)

## D
### Deque

BFS において、Data.Sequence をつかっていては TLE になるケースがあったため、
Data.Vector.Unboxed.Mutable をつかったものを用意した。

- コード片：[IOUQueue](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/IOUQueue.hs)
- [ドキュメント](IOUQueue)
- 使用例：[ABC184E- Third Avenue](https://atcoder.jp/contests/abc184/submissions/19451367)

### Deque （２）

キューがほしければ Data.Sequence をつかう。
両端じゃないキューのときも（大は小を兼ねる的に）。
使用例： [M-SOLUTIONS プロコンオープン D](https://uhideyuki.sakura.ne.jp/studs/index.cgi/ja/atcoder_drills3#2020-03-11p0)

### Dijkstra の単一始点最短経路アルゴリズム

始点を固定したときに、
ほかのすべての頂点との最短路を求める問題を単一始点最短経路問題という。

負の辺がない（閉路がない）場合は、Bellman-Ford 法よりも dijkstra の方が速い。
計算量は、\(|V|\), \(|E|\) をそれぞれ頂点の数、辺の数としたとき、\(\textrm O(|E| \log |V|)\) となる。

コード片：[Dijkstra](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/Dijkstra.hs)

$$<pre>{
-- (node, dist)
type Graph_dijk = VB.Vector (V.Vector (Int, Int))
dijkstra :: Int -> Graph_dijk -> Int -> IO (V.Vector Int)
dijkstra s g numV = ...
$$}

g はグラフを表現する隣接リストで、g VB.! i が i 番目の頂点に接する辺を表現しており、
（行先番号, コスト) のベクター。（Unboxed Vector の Boxed Vector になっていることに注意）

使用例：

- [ABC035D - トレジャーハント](https://abc035.contest.atcoder.jp/submissions/12073938)
- [ABC164E - Two Currencies](https://atcoder.jp/contests/abc164/submissions/12441674)

### Dinic の最大流アルゴリズム

コード片：[Dinic.hs](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/Dinic.hs)

使用例：

- [ABC010D - 浮気予防](https://atcoder.jp/contests/abc010/submissions/12518124)
- ARC074F - Lotus Leaves
- ABC091C - 2D Plane 2N Points

### Divisors, 約数

$$<pre>{
divisors x = divs' x 1 []
  where divs' x i ds | i*i > x        = sort ds
                     | x `mod` i == 0 = divs' x (i+1) (i:(x`div`i):ds)
                     | otherwise      = divs' x (i+1) ds
$$}

使用例：
[ABC112D - Partition](https://atcoder.jp/contests/abc112/submissions/11476026)

## E
### エラトステネスの篩 (Sieve of Eratosthenes)

コード片：[snippets/Primes.hs](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/Primes.hs)

$$<pre>{
primes = sieve [2..]
  where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
$$}

とても有名なこのコードだが、さすがにこれをそのままでは [TLEになる](https://atcoder.jp/contests/abc149/submissions/9425385) ので。

使用例：[ABC149C - Next Prime](https://atcoder.jp/contests/abc149/submissions/9429221)

### EOF

AtCoder では入力の行数がわからないケースはほとんどない気がするのだけど、
いちど見かけたので EOF の扱いについて書いておく。$<verb>{getLines} は EOF
に出くわすとランタイムエラーになるので、これに先立ってチェックする必要がある。

$$<pre>{
import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           System.IO

getLines = glines []
  where glines ls = do
          l <- BS.getLine
          let ls' = ls ++ [l]
          eof <- isEOF
          if eof then return ls' else glines ls'

main = do
  ls <- getLines
  print ls
$$}


使用例： [ABC126D - Even Relation](https://atcoder.jp/contests/abc126/submissions/10481432)

### 拡張ユークリッドの互除法

\(ax + by = \textrm{gcd}(a,\ b)\) を満たす \((x,\ y)\) を一組求めるアルゴリズム:
[ExtEuclid](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/ExtEuclid.hs)

\(a\) の \(\textrm{mod}\ p\) における逆元を求めるためにも使うことができる。
\(x\) が \(a\) の逆元であるとは、

\[
ax \ \equiv \ 1 \ (\textrm{mod}\ p)
\]

が成立することであり、これは、つまり、

\[
ax + py = 1
\]

を満たす y が存在することと等値である。

## K
### クラスカル法 (Kruskal's algorithm)： 最小全域木
ある無向グラフがあったときに、その部分グラフで、かつ、任意の２頂点を連結にするような木を全域木 (Spanning Tree）という。
辺にコストがある場合に、使われる辺のコストの和を最小にする全域木を最小全域木
（Minimum Spanning Tree）という。クラスカル法は最小全域木を求める方法の１つ。

クラスカル法では、すべての辺をコストの順でソートしておき、順番に、まだ連結でない
２頂点をむすぶ辺ならば加えていく。連結成分の判定には Union-Find が使える。

クラスカル法では、辺のソートに一番時間がかかり、計算量は
\(\textrm O(|E| \log |E|)\) となる$<fn>{蟻本には O(|E| log |V|) と書かれているのだが、辺のソートが支配的なのだったら　O(|E| log |E|) なのでは。}。

使用例： 

- [いろはちゃんコンテスト Day2 - D 楽しすぎる家庭菜園](https://atcoder.jp/contests/iroha2019-day2/submissions/12162471)
- [ARC029C - 高橋君と国家](https://arc029.contest.atcoder.jp/submissions/12168778)
- [ARC076D - Built?](https://atcoder.jp/contests/arc076/submissions/12543960)

## M
### modinv : mod p における逆元, modpow : 二分累乗法（大きな n に対する a^n `mod` p) 

コード片： [snippets/ModInv.hs](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/ModInv.hs)

p が素数でない場合には、modinv ではなく拡張ユークリッドの互除法を使う必要がある。

## N
### nextPermutation

コード片： [snippets/NextPermutation.hs](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/NextPermutation.hs)


Data.Vector.Unboxed.Mutable に nextPermutation あったなぁと思ったんだけど、
使ってみたら [CEになってしまった](https://atcoder.jp/contests/abc150/submissions/9398492)
ので用意。
Listは遅いので…とも思ったけど、AtCoder で nextPermutation を使えるケースは、
順列を列挙できるくらいにリストが十分短いか、呼び出し回数が十分少ないかのどちらかだろうから、ま、いっか。

使用例： [ABC150C - Count Order](https://atcoder.jp/contests/abc150/submissions/9414815)

## P
### Prime Factorization, 素因数分解（その１）

コード片：

$$<pre>{
primeFactorization :: Int -> [(Int, Int)]
primeFactorization x = pfact x 2 0 []
  where
    sr = floor $ sqrt $ fromIntegral x
    pfact n i r fs | i > sr    = if n > sr then (n,1):fs else fs
                   | otherwise =
                     if n `mod` i == 0
                     then pfact (n `div` i) i (r+1) fs
                     else pfact n (i+1) 0 (if r > 0 then (i,r):fs else fs)
$$}

使用例：

- [CADDi 2018 C - Product and GCD](https://atcoder.jp/contests/caddi2018/submissions/11406708)
- [ARC067C -  Factors of Factorial](https://atcoder.jp/contests/arc067/submissions/11693643)

### Prime Factorization, 素因数分解（その２）

１つの数に対して素因数分解するのであれば、前項のやりかたでもいいかもしれませんが、
N 個の数 {\(A_i\)} すべてを素因数分解するといった場合には、もっと効率のいいやり方が必要になります → [ABC152E の解説](https://www.youtube.com/watch?v=UTVg7wzMWQc&t=3446) を見よう。

使用例：

- [ABC177E - Coprime](https://atcoder.jp/contests/abc177/submissions/16379359)


### Priority Queue

[Data.Set](http://hackage.haskell.org/package/containers-0.6.2.1/docs/Data-Set.html)
で代用可能。

- $<verb>{deleteFindMin :: Set a -> (a, Set a)}: delete and find the minimal element.
- $<verb>{deleteFindMax :: Set a -> (a, Set a)}: delete and find the maximal element.

[Dijkstra](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/Dijkstra.hs)
で使用した。

値に重複がある場合には、タプルにしてダミーの値と組にするなどして、重複しないようにすれば良い。


## Q
### QuickSort

追記： Data.List.sort が遅くて悲しいケースには、Data.Sequence の unstableSort を使うのもいいかもしれない。
⇒ Seq.unstableSort では [TLE](https://atcoder.jp/contests/iroha2019-day2/submissions/12162135) だが、
QuickSortVec で [AC](https://atcoder.jp/contests/iroha2019-day2/submissions/12162471) になったケースもあったので、すべてこれで代用というわけにはいかないようだ。

コード片： [snippets/QuickSortVec.hs](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/QuickSortVec.hs)

Data.List.sort があまりに遅くて悲しいときむけ。
Data.Vector.Unboxed.Mutable に対してソートする $<verb>{quickSortVec} と、
内部でそれを用いることで List をソートする $<verb>{quickSortList} がある。
以下の使用例では、両方の形を用いた。

使用例：  [ABC040D -  - 道路の老朽化対策について](https://atcoder.jp/contests/abc040/submissions/9522274)


※同じコードでも quickSortVec に型注釈をつけるだけで遅くなったりして不思議： [submissions/9522041](https://atcoder.jp/contests/abc040/submissions/9522041)

⇒ haskell-jp slack で聞いてみたところ、多相な型注釈を書いたことで、コンパイラによる特殊化が阻害されたのではないか？とのこと。GHC のバージョンにもよりそう（GHC 8.6 ではそんなことはない、とも）だが、AtCoder では多相の型注釈はかかないほうが無難っぽい。

## S
### Segment Tree

セグメント木は、数列中の区間を扱うのに適した完全二分木である。

- コード片：[snippet/Segtree](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/Segtree.hs)
- ドキュメント：[Segtree](Segtree)

使用例：

- [ABL D - Flat Subsequence](https://atcoder.jp/contests/abl/submissions/17097409)

### スライド最小値

「長さ n の数列 \(a_0, a_1, \cdots, a_{n-1}\) と数 k が与えられます。
そのとき、\(b_i = \min(a_i, a_{i+1}, \cdots, a_{i+k-1})\) と定義される数列
\(\{b_i\}\) を求めよ。」

Deque をつかうと \(\textrm O(n)\) で解ける。蟻本 p.300 参照。

コード片：
[SlideMin.hs](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/SlideMin.hs)


## U
### UnionFind

コード片： [snippets/UnionFind.hs](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/UnionFind.hs)

無向グラフの連結成分を求める方法。最小全域木を求めるクラスカル法でも用いられる。

使用例： 

- [ABC040D -  - 道路の老朽化対策について](https://atcoder.jp/contests/abc040/submissions/9522274)
- [ARC097D - Equals](https://atcoder.jp/contests/arc097/submissions/12464589)

## W
### Warshall-Floyd の全点対最短経路アルゴリズム

コード片： [snippets/WarshallFloyd.hs](https://github.com/unnohideyuki/AtHaskell/blob/master/snippets/WarshallFloyd.hs)

このコード片自体が、STUArray をもちいた二次元 dp の例にもなっている。

使用例： 

- ABC012D - バスと避けられない運命
- [ABC151D - Maze Master](https://atcoder.jp/contests/abc151/submissions/9471634)
- [ABC179D - Wall](https://atcoder.jp/contests/abc079/submissions/12941300)