AtCoder Library (ACL) は AtCoder が公開しているC++用のライブラリです。ABC のC問題ぐらいまではC++の標準ライブラリでほとんど対応できますが、それ以上のレベルになると（C問題でも時々は）ACL を使用することで劇的に速く簡単に解くことができる場合があります。
ここにライブラリと、そのドキュメント（document_ja フォルダの下）があります。
インストール
AtCoder のサイトの実行環境には ACL は既に組み込まれているので何もする必要ありませんが、パソコンのローカル環境で ACL を動かすにはインストール作業が必要です。以下の説明は Apple Silicon Mac のターミナル、または WIndows WSL でローカル実行環境を整備している場合を想定しています。コンパイラは gcc です。
ACL をインストールするためのディレクトリを作成し（ここでは “ACL” という名前にした）、その中に GitHub からクローンします。
|
1 2 3 |
$ mkdir ACL $ cd ACL $ git clone https://github.com/atcoder/ac-library.git |
インストールした場所に Path を通します。Mac の場合は ~/.zshrc に、Windows WSL の場合は ~/.bashrc または ~/.cshrc に１行追加します。コマンド内に書くパスは自分の環境に合わせてください。追加する場所はファイルの末尾付近で良いでしょう。
|
1 |
export CPLUS_INCLUDE_PATH="$CPLUS_INCLUDE_PATH:/Users/XXX/ACL/ac-library" |
Path を通したらターミナルを再起動します。VSCode のターミナルを使っているなら VSCode を再起動してください。
例えば、ソースコードに
|
1 2 |
#include <atcoder/all> using namespace atcoder; |
と追加してコンパイルしてみてください。正しく Path が通っていればエラーなくインクルードできるはずです。
UnionFind
ACL にはいろいろなクラス・関数が含まれますが、一例として UnionFind を使ってみましょう。UnionFind は DSU（Disjoint Set Union、素集合データ構造）のことですが、競プロの解説などでは「UnionFind」と呼ぶことが多いです。根付き木を使ってグループ分けを効率的に管理するデータ構造です。問題文に「連結成分」というような言葉が出てきたら UnionFind を思い出してください。
実際のクラス・メソッドはこのようになっています。
UnionFind のアルゴリズム解説は次のページのスライドショーが非常にわかりやすいです。例題もあるので解いてみてください。
別の例題をいくつか解くと理解が深まります。グラフを使っても解けるので、UnionFind を使った場合と比べてみることをおすすめします。
https://atcoder.jp/contests/abc284/tasks/abc284_c
https://atcoder.jp/contests/abc288/tasks/abc288_c
Python
調べた限りでは AtCoder は Python 版の UnionFind を出していないようですが、ネット検索すると Python でライブラリ化した実装例がたくさん見つかります。適当なものを選んでテンプレート化しておくと良いです。クラス名やメソッド名は AtCoder の UnionFind に合わせたものを使えば解説を見たときに混乱することも少ないでしょう。
例）
