この記事は
D言語 Advent Calendar 2019
12日目の記事です。
大学でD言語はいいぞと言い続けていたら感染開眼したD言語erとの共著です。
この記事は前後編に分かれているうちの後編です。
前編はD言語くん Advent Calendar 12日目の記事として投稿されています。
前編の内容も非常に重要で示唆に富んでいるので必ず見ましょう。
競技プログラミングでは十分に速いプログラムをできるだけ短時間で書き上げる必要があります。 言語そのものが低速だと想定解のアルゴリズムが書けたとしても定数倍で不正解にされてしまうことがまれにあります。 また、普通に書いていても言語仕様の穴に頻繁に引っかかるような言語では高速なプログラミングは難しいでしょう。 その点、D言語は競プロ(競技プログラミング)向けの言語です。 速度と書きやすさとを両立しており、標準ライブラリも充実しています。
AtCoderでは使用言語にD言語が選べます。
執筆時点ではバージョンが古いためimport std;ができない等不便な点がありますが、
最近大学でC++ばっか書いてて最新情報を追えてないので都合が良い
近いうちアップデートを行うそうなので期待して待ちましょう。
標準ライブラリ、把握できてますか
そんなD言語ですが、その魅力を競プロのために最大限活かすのは大変です。 標準ライブラリに需要を満たす関数があることに気づかず、自分で実装してしまうことも多いです。 もちろんD言語は速いので自前実装でもきちんと書けていれば速度で困ることはないでしょうし、 競プロで必要なデータ構造やアルゴリズムをいちどは自分で実装してみることには大きな意味があります。 しかし競プロではバグりにくいプログラミングをするのも大切です。 仕組みを理解できているのに実装でミスってバグを出してしまうくらいなら標準ライブラリを使っちゃいましょう！
というわけで今回はstd.containerの中で競プロで使えそうなものを紹介します。
DList
双方向連結リストです。 キューにもスタックにもなる便利なやつです。
rootノードが先頭と末尾のノードにつながっているリング状の構造をしているタイプの双方向連結リストのようです。 先頭/末尾要素の削除が$O(1)$でできます。 ドキュメントには先頭/末尾への挿入操作が$O(\log(n))$と書いてありますが、 ソース見る限り 1要素の時は$O(1)$でできているように見えます。 挿入系関数にはレンジも渡せるのですが、それはレンジの長さに対して$O(n)$かかっているように見えます。 $O(\log(n))$要素どこ……？$n$とは……？
DList!(long) dl;
dl.insertBack(1); // 末尾に挿入
dl.insert(2); // 上のエイリアス
dl.insertFront(3); // 先頭に挿入
assert(dl.front == 3); // 先頭要素
assert(dl.back == 2); // 末尾要素
dl.removeFront(); // 先頭要素を削除
dl.removeBack(); // 末尾要素を削除
assert(dl.front == 1);
assert(dl.back == 1);
Iterableなのでforeachやreduce、arrayに渡せます。
デバッグ用に全体を表示したいときはarrayで配列にします。
auto dl = DList!(long)([1, 2, 3, 4, 5]);
foreach (x; dl)
writeln(x);
dl.reduce!(max)().writeln();
dl.writeln();
dl.array().writeln();
// 出力
// 1
// 2
// 3
// 4
// 5
// 5
// DList!long(7FCF7A443020)
// [1, 2, 3, 4, 5]
以下のように再帰で書かれた深さ優先探索プログラムがあったとします。
void dfs(T arg)
{
if (/* ... */) // 終了条件
return;
// do something...
// 再帰
dfs(a);
dfs(b);
}
void main()
{
dfs(x);
}
これはDListをスタックとして使って以下のように変換できます。
void main()
{
DList!T stack;
stack.insert(x);
while (!stack.empty)
{
T arg = stack.back;
stack.removeBack();
if (/* ... */) // 終了条件
continue;
// do something...
// 再帰
stack.insert(b);
stack.insert(a);
}
}
状況に合わせて書きやすい方を使っていきましょう。
キューとして使うと幅優先探索ができます。
void main()
{
DList!T Q; // queueって打ちにくくない？
Q.insert(x);
while (!Q.empty)
{
T arg = Q.front;
Q.removeFront();
if (/* ... */) // 終了条件
continue;
// do something...
Q.insert(a);
Q.insert(b);
}
}
BinaryHeap
二分ヒープです。 ヒープソートのあれですね。 競プロではプライオリティキューとか優先度付きキューとか呼ばれていて、 今まで挿入した要素の中で最大のものが最初に出てくるキューとして使います。
二分ヒープは二分木を使ったヒープ構造を作ることで最大値の取得が高速にできます。 具体的には入っている要素数$n$に対して値の追加と最大値の削除が$O(\log(n))$で可能です。
BinaryHeapはランダムアクセス可能な列構造の上にヒープを構成します。
競プロでBinaryHeapを使う際は以下のようにstd.container.arrayのArrayを使って書くと手軽です。
BinaryHeap!(Array!long) bh;
書くのがめんどくさいためエイリアスをはっておきます。
alias PQueue = BinaryHeap!(Array!long);
するとこのように優先度付きキューを使うことができます。
PQueue pq;
foreach (x; [0, 1, 9, 2, 8, 3, 7, 4, 6, 5])
pq.insert(x);
foreach (_; 0 .. pq.length)
{
writeln(pq.front);
pq.removeFront();
}
// 9
// 8
// 7
// 6
// 5
// 4
// 3
// 2
// 1
// 0
さらに、大小比較の方法を変えたり、要素の型を変えたりするためにエイリアステンプレートにすると便利でしょう (執筆中に気がついた) 。
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);
PQueue!long pq1;
PQueue!(long, "b<a") pq2; // 最小値が取り出せるようになる
InputRangeなのでInputRangeを受け取ることのできる関数が使えます。
使えたからといってどう役に立つのかすぐには思いつきませんが……。
RedBlackTree
赤黒木です。
大小比較可能な要素の追加、削除、探索が$O(\log(n))$でできます。
連想配列でbool[T]とやるより集合を自然に扱えます。
また、連想配列と違って最悪計算量が$O(\log(n))$であるという安心感があります。
ただ、AtCoderでは基本的に連想配列を攻撃するような入力は来ないので大抵の場合では連想配列のほうが速いです。
auto rb = new RedBlackTree!long();
rb.insert(1); // 追加
rb.insert(2);
rb.insert(3);
rb.removeKey(2); // 削除
writeln(rb);
writeln(1 in rb);
writeln(2 in rb);
// RedBlackTree([1, 3])
// true
// false
上の2つと違って初期化の際はnewするので注意しましょう。