AtCoder
コンテスト参加記録や解法記事など
Recent Contests
View all →| Date | Contest | Rank | Performance | New Rating | Solution |
|---|
Recent Solutions
View all →Loading...
Library
View all →
整数論
幾何
グラフ
データ構造
木
二項係数 (nCr)
階乗テーブルを前計算して ${}_n\mathrm{C}_r$・${}_n\mathrm{P}_r$・${}_n\mathrm{H}_r$ や、同じものを含む順列の個数を素数 $p$ を法として求める
凸包
Andrew のアルゴリズム(Monotone Chain)で凸包を求める(外積・面積・格子点の数付き)
Dijkstra
非負整数の重みを持つグラフの単一始点最短路(経路復元付き)
遅延セグ木(ACL)の使い方
ACL の LazySegTree に渡す関数を、区間加算・区間更新・区間アフィン変換と、区間の最小値・最大値・和などの組み合わせごとにまとめる
LCA
ダブリングで最小共通祖先・2 頂点間の距離・$k$ 個上の祖先・パス上の $k$ 番目の頂点を求める