Shirotsume の日記

嘘Greedyを生やすな

ACLを使ってみよう!

この記事は 競プロ Advent Calendar 2022 の二日目として書かれた記事です。#競プロAdC

Nachia さんによる先日の記事 競プロAdC やってるみたいなので Library Checker の解法紹介をぶっこむ | Mathenachia に引き続き、ライブラリについてのお話です。主に対象とする読者層はAtCoder茶色以上くらいで、どんなアルゴリズムの勉強をしたらいいんだろう?と悩んでいるような人です。暖色の人に有用な情報はあんまりなさそうです。

ライブラリについて

AtCoder などでの競技プログラミングでは、計算量で差がつくアルゴリズムがよく出題されます。有名な方法は特に何度も出題されるので、あらかじめプログラムを用意しておきます。競プロ文脈でライブラリというと、この事前に用意したプログラムのことを基本的に指します。

ライブラリは自分で作ってもよいですが、他の人が作ったものを借りてくるという方法もあります。今回私がおすすめするのは、 AtCoder Library を有効活用する方法です。

AtCoder Library について

AtCoder Library (ACL) は AtCoder によって公式に提供されている C++ 用のライブラリです。UnionFind や最大フローなど、よく出題されるアルゴリズム/データ構造から、FloorSum のようなコンテストではあんまり見たことのないものまで数多く取り揃えてあります。

https://atcoder.github.io/ac-library/document_ja/ ←ドキュメントです。ここに使い方が載っているので、調べて使うことができます。ここからダウンロードもできます。

ACL を使う利点を以下に示します。

  • AtCoder により公式に動作テストがなされており、非常に高速に動作する
  • あらかじめ AtCoder のジャッジサーバに組み込まれているので、コピペをする必要がない
  • ABC 等のコンテストで出題されやすいアルゴリズムがそろっている
  • AtCoder Library Practice Contest でいろいろ試してみることができる

他にもありそうです。特に、アルゴリズム/データ構造をどこから勉強していいかわからない…と困っている茶色~緑コーダーは、ACLの使い方を順番に勉強していくとよいと思います。*1

例えば A - Disjoint Set Union は次のコードでACできます。(本当に、これをそのまま提出欄に貼ればACです)ライブラリを貼る必要がないので、非常に短く済んでいることが分かると思います。*2

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
int main(void)
{
    int n, q;
    cin >> n >> q;
    dsu U(n);
    int t, u, v;
    while(q--){
        cin >> t >> u >> v;
        if(t){
            cout << (U.same(u, v) ? 1 : 0) << endl;
        }
        else{
            U.merge(u, v);
        }
    }
}

ここまで C++ の話をしましたが、有志による ACL の他言語版が用意されているため、 C++ ユーザ以外はそれを利用することができます。

参考

ここで力尽きたので、過去に書いたACL紹介スライドを貼っておきます。各アルゴリズム/データ構造のざっくりとした説明はここをご覧ください。

*1:灰色コーダーは、まずはSTLに入っているような標準的なデータ構造(dequeとかsetとか)や、より基本的なアルゴリズム(全探索、DFS、 BFS)から勉強することをお勧めします。ABC-C問題まででACLに入っているアルゴリズムが必要になる問題が出ることはほとんどないと思います。

*2:余談ですが、これのコードを提出しようとしたとき間違えて記事全体をコピペしてしまい、事前に記事を公開してしまって終わりになっています。暇な人は探してください