Nim-ACL

Appendix / FAQ

動作環境

インストール方法

g++ / clang++へのインストール方法

一番わかりやすい方法は、トップページに書いたように、main.cppと同じ場所にatcoderフォルダを置いて、g++ main.cpp -std=c++14 -I .と実行することです。ここで、.はフォルダを表す記号です(本当に I の後にスペース、点、と入力します。)

atcoderフォルダをいちいちコピーしたくない場合は以下のような方法があります。

Visual Studioへのインストール方法

古いVisual Studioを使っている場合、アップデートしてください。Visual Studio 2017 / 2019をサポートしています。

Visual Studioがインストールされているならば、以下のようなフォルダがあるはずです。

このなかに丸ごと atcoder フォルダをコピーしてください。つまり、

となるように配置してください。

他のジャッジへの提出方法

expander.pyというスクリプト(python3.5 or later)を用意しています。 python3 expander.py main.cppと実行するとcombined.cppが生成され、これは他のオンラインジャッジに提出できる形になっています。

テストはしていますが、サポート保証外です。

ドキュメントの表記法 / 明記されていないこと

💻マーク

C++初心者には難しいかもしれない機能を表すマークです。AC Libraryは、このマークの付いた箇所を無視してもアルゴリズム的に困らないように設計されています。modintなどが該当します。

テンプレート関数

例えばsuffix_array(v)はvector<int>, vector<ll>などを引数に取れるのですが、これらをまとめてsuffix_array<T>(vector<T> v)と表記します。

例えばvector<int>に格納された整数列 $v$ の suffix array を求めたいとき、

vector<int> sa = suffix_array(v);
// vector<int> sa = suffix_array<int>(v); ではないことに注意

と使います。

デフォルトコンストラクタ

構造体、例えばscc_graph などは、サンプルのように

#include <atcoder/scc>;
using namespace atcoder;

int main() {
    int n;
    scanf("%d", &n);
    scc_graph g(n); // n 頂点からなるグラフを生成
    return 0;
}

といった宣言方法だけでなく、次のように初期化なしで宣言することも出来ます。

#include <atcoder/scc>;
using namespace atcoder;

scc_graph g;

int main() {
    return 0;
}

このように宣言したときの挙動（デフォルトコンストラクタ）は、

となります。また、構造体に後から代入することも出来ます。

#include <atcoder/scc>;
using namespace atcoder;

scc_graph g;

int main() {
    g = scc_graph(10);
    return 0;
}

辺の型

最大流ライブラリなどでは、辺の型として mf_graph<Cap>::edge というのを使います。

例えば、mf_graph<int> の辺の型は mf_graph<int>::edge です。 :: が見慣れないかもしれないですが、mf_graph<int>::edge という文字列をintやstringのように扱えばよいです。例えば

vector<mf_graph<int>::edge> v;
mf_graph<int>::edge e;

のようになります。

デフォルトテンプレート引数

convolution のように、以下のような表記法を用いることがあります。

vector<T> convolution<int m = 998244353>(vector<T> a, vector<T> b)

これは、二通りの使い方ができることを表します。

vector<long long> c = convolution(a, b);
vector<long long> c = convolution<924844033>(a, b);

上段のように使った場合は、$m$ の値は自動的に $998244353$ となります。 下段のように使った場合は、$m$ の値は明示的に与えた値 (この場合は $924844033$) となります。

Segtree / LazySegtree の厳密な要件

Segtree / LazySegtree を使いたい状況において、扱う代数構造が無限集合である場合があります。たとえば、与えられた区間の $\mathrm{max}$ を求める、与えられた区間内の全ての要素に定数を足す、の二種類のクエリに対応する LazySegtree はよくありますが、このときたとえば $S = \mathrm{int}$ としてしまうと、$S$ は加法について閉じていない (overflow を起こす可能性がある) ため、厳密な意味でドキュメント本編の制約を満たしません。そこで、AC Library では以下のような場合正しく動くことを保証しています。

Segtree

LazySegtree

たとえば、最初の例で自然に $(S, F)$ を定めると以下のようになりますが、これは無限集合です。

$(S', F')$ を以下のように定めることで、制約が十分小さければこのライブラリで扱うことができます。

maxflowの挙動

内部では各辺 $e$ について $2$ つの変数、流量 $f_e$ と容量 $c_e$ を管理しています。頂点 $v$ から出る辺の集合を $\mathrm{out}(v)$, 入る辺の集合を$\mathrm{in}(v)$ 、また頂点 $v$ について $g(v, f) = \sum_{e \in \mathrm{in}(v)}{f_e} - \sum_{e \in \mathrm{out}(v)}{f_e}$ とします。

flow(s, t)

これを呼ぶと各辺の流量を変更します。厳密には変更前と変更後の流量を $f_e$, $f'_e$ として、以下の条件を満たすように変更します。

min_cut(s)

各辺 $e = (u, v, f_e, c_e)$について、$f_e \lt c_e$ ならば辺 $(u, v)$ を張り、$0 \lt f_e$ ならば辺 $(v, u)$ を張ったと仮定したとき、頂点 $s$ から到達可能な頂点の集合を返します。

change_edge(i, new_cap, new_flow)

辺 $i$ の流量、容量のみを new_flow, new_cap へ変更します。