AtCoder 色別ライブラリガイド

このページでは、Nim-ACL のライブラリを AtCoder のおおまかな色帯に合わせて分類します。

分類は絶対的なものではありません。同じアルゴリズムでも、問題への気づき方や他の技法との組み合わせによって難易度は大きく変わります。

ここでは、次の目安を使います。

AtCoder 公式講座との関係

このページの「初級・中級・上級」は Nim-ACL 独自の利用頻度・色帯分類です。 AtCoder Algorithm Lectures の難易度 1〜9 とは別の指標です。

公式講座との対応状況は AtCoder Algorithm Lectures 対応表 を参照してください。

記号

• 必須：その色帯で優先して覚えたい
• 推奨：出題頻度が高く、覚える価値が大きい
• 発展：特定の問題で非常に強い
• 内部・高度：利用よりも実装理解や特殊用途向け

初級：緑以下

初級では、難しい data structure を大量に覚えるより、

1. 配列・文字列を整理する
2. graph を正しく走査する
3. prefix sum や DSU で計算量を落とす
4. よく出る定型処理をライブラリ化する

ことが重要です。

最初に覚えたいもの

ACL 本体で優先して覚えるもの

次の module は競技プログラミングの基礎です。

import atcoder/dsu
import atcoder/fenwicktree
import atcoder/segtree
import atcoder/modint

DSU

無向 graph の連結成分を管理します。

典型的なキーワード：

• 頂点を順に結ぶ
• 同じ連結成分か
• 連結成分サイズ
• Kruskal

Fenwick Tree

点加算・prefix sum に向いています。

典型的なキーワード：

• inversion number
• prefix sum を更新付きで求める
• 座標圧縮後の頻度管理

Segment Tree

区間積・点更新を扱います。

典型的なキーワード：

• 区間最小・最大・和
• 点更新
• 二分探索付き区間 query

初級のおすすめ学習順

1. Run-Length Encoding
2. Coordinate Compression
3. Cumulative Sum
4. DSU
5. Fenwick Tree
6. Dijkstra
7. Topological Sort
8. Segment Tree
9. Functional Graph / Doubling
10. KMP

初級の逆引き

中級：青以下

中級では、問題の構造に応じて data structure を選ぶ力が重要になります。

「とりあえず Segment Tree」ではなく、

• 静的か動的か
• 演算が冪等か
• query が online か offline か
• XOR や文字列に特別な構造があるか

を見分けます。

区間 query・集合

最適化 DP・直線集合

XOR・数学

文字列

木 DP

中級のおすすめ学習順

1. Lazy Segment Tree
2. Sparse Table
3. Disjoint Sparse Table
4. Binary Trie
5. XOR Basis
6. Manacher
7. Rolling Hash
8. Mo's Algorithm
9. Rerooting DP
10. Wavelet Matrix
11. Convex Hull Trick
12. Li Chao Tree

区間 data structure の使い分け

文字列の使い分け

上級：黄以上

上級では、単独のアルゴリズムを知っているだけではなく、

• offline 化
• rollback
• 木や graph の圧縮
• 複数 data structure の組み合わせ
• 問題固有の invariant

が必要になります。

動的 graph・rollback

DSU の使い分け

木の圧縮・subtree query

無向 graph 分解

Low-link 系の使い分け

高度な文字列

回文 algorithm の使い分け

多項式・高度な数学

高度な静的・永続区間 data structure

高度な graph

次の分野は、出題頻度は低めですが、必要な問題では代替が難しいです。

import atcoder/extra/graph/chu_liu_edmonds
import atcoder/extra/graph/boruvka

• Chu-Liu/Edmonds：有向最小全域木
• Borůvka：component 単位の最小全域木
• Dominator Tree：有向 graph の支配関係
• Mo on Tree：木上の offline path query

上級のおすすめ学習順

1. Rollback DSU
2. Offline Dynamic Connectivity
3. Virtual Tree
4. DSU on Tree
5. Biconnected Components
6. Two-Edge-Connected Components
7. Block-Cut Tree
8. Suffix Automaton
9. Palindromic Tree
10. FPS
11. Link-Cut Tree
12. Dominator Tree

目的別の逆引き

XOR

回文

木

graph connectivity

文字列検索

コンテスト別の目安

ABC A〜C

優先度が高いもの：

• Run-Length Encoding
• Coordinate Compression
• cumulative sum
• basic graph traversal
• DSU
• modint

ABC D〜E

優先度が高いもの：

• Fenwick Tree
• Segment Tree
• Dijkstra
• Functional Graph / Doubling
• KMP
• MexSet
• SortedSet / SortedMap
• Rerooting DP

ABC F・ARC

優先度が高いもの：

• Lazy Segment Tree
• Binary Trie
• XOR Basis
• Sparse Table
• Disjoint Sparse Table
• Mo
• Wavelet Matrix
• Manacher
• Aho-Corasick
• Convex Hull Trick
• Li Chao Tree

ARC 上位・AGC・Codeforces Div.1

候補：

• Rollback DSU
• Offline Dynamic Connectivity
• Virtual Tree
• DSU on Tree
• Biconnected Components
• Block-Cut Tree
• Suffix Automaton
• Palindromic Tree
• FPS
• Link-Cut Tree

今後の追加候補

Nim-ACL で今後優先したい候補です。

初級〜中級

• Z Algorithm の使いやすい facade
• Prefix Sum facade の統一
• Monotonic Queue / Stack helper
• Interval Set

中級

• Mo with Updates
• Persistent Binary Trie
• Static Range Frequency facade
• Matrix utility
• Miller-Rabin
• Pollard Rho

上級

• Dominator Tree
• Mo on Tree
• Segment Tree Beats facade
• Dynamic Tree DP
• Li Chao Tree persistent version
• General matching / blossom
• Min-plus convolution 系

学習方針

ライブラリを暗記するより、次を説明できる状態を目指すのがおすすめです。

1. 何を高速化するアルゴリズムか
2. 素朴解は何計算量か
3. 前提条件は何か
4. update/query が online か offline か
5. 使用する data structure の invariant は何か
6. 似たライブラリとどう使い分けるか

Nim-ACL の高度な module では、API だけでなく「概要・使いどころ・考え方」も記載していきます。