組み込み型である Int のサイズ（表現可能な値の範囲）は環境依存だが、 AtCoder は 64-bit 環境であるらしく、基本的に整数型としては Int を使えばよい。
main = do print (maxBound::Int) print (minBound::Int)
↑これを、AtCoder の「コードテスト」で実行した結果が↓
9223372036854775807 -9223372036854775808
始点を固定したときに、 ほかのすべての頂点との最短路を求める最短経路問題を解くアルゴリズムのひとつ。 Dijkstra に比べ遅いが、閉路がある場合にも対応できる。
コード片： BellmanFord
shortestPath :: Int -> V.Vector (Int, Int, Int) -> Int -> IO (Maybe (V.Vector Int)) shortestPath s edges numV = ...
このコードは、閉路がない場合には単一始点最短経路問題の答えを返し、 閉路があった場合には Nothing を返す。
終点も固定した、２頂点対最短経路問題にも使用できるが、 その場合、２頂点間の経路に関係のない箇所に閉路があっても差し支えないため、 上述のアルゴリズムそのままでなく、改造が必要となる。 （「２週目」にも更新があったノードの距離を Inf とする）
※改造せずにもちいて、２頂点間に関係ない閉路を検出してしまい WA
ABC137E の入力例３も見よ。
使用例：
コード片： snippets/bisect.hs
Python の bisect_right, bisect_left を一般化して、関数を引数にとる形にして移植。 整列済の配列などコレクションに対して使えるのはもちろん、AtCoder で頻出の判定関数を引数にとることもできる。
配列中に、検索対象と等しい値がひとつ以上あったときに、 BisectRight はそれらの一番右のものより、さらに右隣りのインデックスを返す。 BisectLeft は、それらの一番左のもののインデックスを返す。
配列中に、検索対象と等しい値がなかった場合には、検索対象よりも大きな要素のうち最小のもののインデックスを返す（Right/Left 共通）
使用例：
BFS において、Data.Sequence をつかっていては TLE になるケースがあったため、 Data.Vector.Unboxed.Mutable をつかったものを用意した。
キューがほしければ Data.Sequence をつかう。 両端じゃないキューのときも（大は小を兼ねる的に）。 使用例： M-SOLUTIONS プロコンオープン D
始点を固定したときに、 ほかのすべての頂点との最短路を求める問題を単一始点最短経路問題という。
負の辺がない（閉路がない）場合は、Bellman-Ford 法よりも dijkstra の方が速い。 計算量は、\(|V|\), \(|E|\) をそれぞれ頂点の数、辺の数としたとき、\(\textrm O(|E| \log |V|)\) となる。
コード片：Dijkstra
-- (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 になっていることに注意）
使用例：
コード片：Dinic.hs
使用例：
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
コード片：snippets/Primes.hs
primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
とても有名なこのコードだが、さすがにこれをそのままでは TLEになる ので。
AtCoder では入力の行数がわからないケースはほとんどない気がするのだけど、 いちど見かけたので EOF の扱いについて書いておく。getLines は EOF に出くわすとランタイムエラーになるので、これに先立ってチェックする必要がある。
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
\(ax + by = \textrm{gcd}(a,\ b)\) を満たす \((x,\ y)\) を一組求めるアルゴリズム: ExtEuclid
\(a\) の \(\textrm{mod}\ p\) における逆元を求めるためにも使うことができる。 \(x\) が \(a\) の逆元であるとは、
\[ ax \ \equiv \ 1 \ (\textrm{mod}\ p) \]
が成立することであり、これは、つまり、
\[ ax + py = 1 \]
を満たす y が存在することと等値である。
ある無向グラフがあったときに、その部分グラフで、かつ、任意の２頂点を連結にするような木を全域木 (Spanning Tree）という。 辺にコストがある場合に、使われる辺のコストの和を最小にする全域木を最小全域木 （Minimum Spanning Tree）という。クラスカル法は最小全域木を求める方法の１つ。
クラスカル法では、すべての辺をコストの順でソートしておき、順番に、まだ連結でない ２頂点をむすぶ辺ならば加えていく。連結成分の判定には Union-Find が使える。
クラスカル法では、辺のソートに一番時間がかかり、計算量は \(\textrm O(|E| \log |E|)\) となる*1。
使用例：
コード片： snippets/ModInv.hs
p が素数でない場合には、modinv ではなく拡張ユークリッドの互除法を使う必要がある。
Data.Vector.Unboxed.Mutable に nextPermutation あったなぁと思ったんだけど、 使ってみたら CEになってしまった ので用意。 Listは遅いので…とも思ったけど、AtCoder で nextPermutation を使えるケースは、 順列を列挙できるくらいにリストが十分短いか、呼び出し回数が十分少ないかのどちらかだろうから、ま、いっか。
コード片：
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)
使用例：
１つの数に対して素因数分解するのであれば、前項のやりかたでもいいかもしれませんが、 N 個の数 {\(A_i\)} すべてを素因数分解するといった場合には、もっと効率のいいやり方が必要になります → ABC152E の解説 を見よう。
使用例：
Data.Set で代用可能。
Dijkstra で使用した。
値に重複がある場合には、タプルにしてダミーの値と組にするなどして、重複しないようにすれば良い。
追記： Data.List.sort が遅くて悲しいケースには、Data.Sequence の unstableSort を使うのもいいかもしれない。 ⇒ Seq.unstableSort では TLE だが、 QuickSortVec で AC になったケースもあったので、すべてこれで代用というわけにはいかないようだ。
コード片： snippets/QuickSortVec.hs
Data.List.sort があまりに遅くて悲しいときむけ。 Data.Vector.Unboxed.Mutable に対してソートする quickSortVec と、 内部でそれを用いることで List をソートする quickSortList がある。 以下の使用例では、両方の形を用いた。
※同じコードでも quickSortVec に型注釈をつけるだけで遅くなったりして不思議： submissions/9522041
⇒ haskell-jp slack で聞いてみたところ、多相な型注釈を書いたことで、コンパイラによる特殊化が阻害されたのではないか？とのこと。GHC のバージョンにもよりそう（GHC 8.6 ではそんなことはない、とも）だが、AtCoder では多相の型注釈はかかないほうが無難っぽい。
セグメント木は、数列中の区間を扱うのに適した完全二分木である。
使用例：
「長さ 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
コード片： snippets/UnionFind.hs
無向グラフの連結成分を求める方法。最小全域木を求めるクラスカル法でも用いられる。
使用例：
このコード片自体が、STUArray をもちいた二次元 dp の例にもなっている。
使用例：