D言語の競技プログラミング用ライブラリを作ってみた

タイトルに反して実は作り始めたのは1.5年ぐらい前ですが…

結構安定してきたんで紹介をします。でも使うのはオススメできないかも(いろいろ壊れてるかもしれないため)。要するにせっかく作ったから見てくれというやつです。

準備

  • まずD言語のコンパイラをインストールします

  • D言語のパッケージ管理システムdubをインストールします(https://code.dlang.org/)

  • お好きなところにA.dを作って，sample.dをコピペします(このリポジトリをcloneする必要はないです)

  • dub build --single A.dと打ちます

  • ./Aができない→どうしてこんなことに…
  • ./Aができた→こちらを想定します

sample.dは以下のようになっているはずです

/+ dub.sdl:
    name "A"
    dependency "dunkelheit" version="1.0.0"
+/

import std.stdio, std.algorithm, std.range, std.conv;
import dkh.foundation, dkh.scanner;

int main() {
    Scanner sc = new Scanner(stdin);
    scope(exit) assert(!sc.hasNext);
    int a, b;
    int[] c;
    sc.read(a, b, c);
    writeln(a, b, c);
    return 0;
}

このコードは，整数2個と配列1個を入力して出力するコードです。例えば'./A'を実行して

1 2
3 4 5

と入力すれば，

12[3, 4, 5]

と出力されるはずです

dependency "dunkelheit" version="1.0.0"でversion1.0.0を指定しています。もし今後後方互換性壊したりしても，とりあえずv1.0.0を指定しておけばv1.0.0が動く！すごい！

ソースコード結合

提出するときにはソースコードを1つにする必要があります。ここで

dub run dunkelheit:combine -- -i=A.d -o=A_submit.d -c -u

と打つと，A_submit.dが出来ます。これをそのまま提出すれば動くはずです。多分。

ドキュメント

ライブラリにはドキュメントがついています(ついていない部分もあります)。 https://yosupo06.github.io/dunkelheit/で見ることが出来ます。

機能紹介

いくつか機能を紹介します。

Scanner(dkh.scanner)

一番使います。

サンプルのように読み込みたいものを全部引数に入れてsc.read()を呼べばよいです。

scope(exit)はこのスコープ(= int main)を抜けたときに実行するという意味で，sc.hasNextは全部読み込み終わったかを返すので，要するにscope(exit) assert(!sc.hasNext)はmain関数を抜けたときに全部読み込み終わってるかチェックしてくれます。

また，配列型は，「次のトークンから行が変わるまで全部読み込む」をやるので，

N M
a_1, a_2, ..., a_N

みたいなのを読み込みたいときに便利です(sc.read(N, M, a))。

N M
a_1 b_1
a_2 b_2
:
a_N b_N

みたいなのはどうしようもないです。

Segtree(dkh.container.segtree)

やっぱりライブラリと言ったらsegtree, segtreeと言ったらライブラリみたいなところがあるよね。

D言語はラムダを短くかけるので，

auto seg = LazySeg!(int, int, (a, b) => max(a, b), (a, b) => a+b, (a, b) => a+b, 0, 0)(n); でstarry sky treeが出来ます。

auto seg = LazySeg!(int, int, max, "a+b", "a+b", 0, 0)(n) とも書けます。

dkh.datastructure.segtree のexamplesに詳しく書いています。seg[0..3].sum()で区間取得とかseg[0..2] += 10で区間加算とかお気に入り(自画自賛)

modint(dkh.modint)

scannerの次ぐらいに使います。自動mod取り構造体とも呼ばれます。

alias Mint = ModInt!(10^^9 + 7)

で，

Mint a = Mint(10);
Mint b = Mint(11);
writeln(a+b); //21
writeln(a-b); //1000000006
writeln(a*b); // 110
writeln(a/b); // 逆元も
writeln(a^^b); // べき乗も！

のように使えます。また，dkh.numeric.convolutionをimportすればfftも使えます

Mint[] a, b;
writeln(multiply(a, b));

とか

CI

D言語にはunittestを書きやすい支援機能がついているので，使いました。 githubにpushするたびにdroneが走って，いろんなバージョンでチェックしてくれます。

f:id:yosupo:20180529021956p:plain

↑こんな感じ

なので一度潰したバクは(理論上)再発しないですね！安心！

なお，CIにはhttps://github.com/drone/droneを使ってます，便利