D言語で競技プログラミング

D言語で競技プログラミングをやってみたい…でもなかなか踏み出せない…

実はそんな人が相当数居るはず[要出典]なので，宣伝記事を書きます

主な対象読者

既に競技プログラミングをしており，C++を使っている

Javaを使っている人も対象ですが，基本的にC++よりここがいい！みたいな書き方をします。また，D言語はC++からの移行のしやすさを売りにしています。

なお，この記事には「お前これC++でも出来るんやが」が含まれている可能性があります。その場合ぜひ教えてください。私はC++も使うので，ぜひ知りたいです。

「お前これも便利やろが」も含まれていると思います。それもぜひ教えてください。

この記事を読んで興味がわきました！

D言語を始めよう - D言語ツアー D言語公式のチュートリアルです
競技プログラミングのためのD言語 (1/2) - cafelier@SRM - TopCoder部インターネットしてたら見つけました。非常に有用です。

いろいろ出力できる

D言語では，基本的になんでもwriteln(=c++のprintf)出来ます。

例えば，vectorもそのまま出力できます。

import std.stdio;

int main() {
    int[] v = [1, 2, 3]; // vector<int> v = {1, 2, 3}
    writeln(v);
    return 0;
}

[1, 2, 3]

それだけでなく，structも出力可能です

import std.stdio;

struct Edge {
    int to;
    int dist;
}

int main() {
    Edge e = Edge(1, 2);
    writeln(e);
    return 0;
}

Edge(1, 2)

また，structにtoStringという関数を実装すれば，それが使用されます。

import std.stdio;

struct Edge {
    int to;
    int dist;
    string toString() {
        return "I'm edge";
    }
}

int main() {
    Edge e = Edge(1, 2);
    writeln(e);
    return 0;
}

I'm edge

ライブラリ等に適切にtoStringを実装すれば…夢が広がりますね。 segtreeライブラリに，現在の要素の一覧を出力させたり出来ます。

高階関数

D言語では高階関数が使用可能です。これにより，配列などに対する処理がきれいに書けます

import std.stdio, std.algorithm;

int main() {
    int[] v = [1, 2, 3];

    writeln(v.sum); // 1 + 2 + 3
    writeln(v.map!(x => 2*x)); // [2, 4, 6]
    writeln(v.fold!min); // min(1, 2, 3)
    return 0;
}

6
[2, 4, 6]
1

std.algorithm - D Programming Language ここに様々な高階関数が用意されています。

配列外アクセスをすると怒られる

import std.stdio;

int main() {
    int[] v = [1, 2, 3];
    writeln(v[100]);
    return 0;
}

以下のコードは動くでしょうか？当然動きませんし，動くべきではありません。ですが，C++ではこのようなコードが動いてしまうことが多々あります。これは経験のある方が多いのではないでしょうか？

このコードを実行すると，以下のようになります。

core.exception.RangeError@B.d(5): Range violation
----------------
??:? _d_arrayboundsp [0x4378c2]
??:? _Dmain [0x43701c]

このように，5行目でRange violation，つまり配列外アクセスをしたというメッセージを残して異常終了します。

D言語ではデフォルトで配列外アクセスのチェックがonになっており，簡単に気づけるようになっています。

もちろんパフォーマンスの心配もありません。コンパイル時に-releaseと付ければ配列外アクセスはoffになります。

UFCS

D言語にはUFCS(Uniform Function Call Syntax)と呼ばれる構文糖衣があります。これは，

f(a)
f(a, b, c)

のような関数呼び出しを，

a.f() or a.f
a.f(b, c)

のように書ける，つまり第一引数を外に出せる+引数が一つならカッコを消せる，というだけの機能です。

とてもシンプルな機能に見えますが，これが非常に強力です。

例えば，

int main() {
    vector<int> v = {1, 1, 4, 5, 1, 4};
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    // v = {1, 4, 5}
    return 0;
}

これは，座標圧縮のコードです。

これをD言語で書くと

import std.stdio, std.algorithm, std.range;

int main() {
    int[] v = [1, 1, 4, 5, 1, 4];
    v = array(uniq(sort(v)));
    writeln(v);
    return 0;
}

となります，begin/endが消えてるのは，C++のようにiteratorではなく，rangeと呼ばれるものがベースになっているからです。

これにUFCSを使うと，

import std.stdio, std.algorithm, std.range;

int main() {
    int[] v = [1, 1, 4, 5, 1, 4];
    v = v.sort.uniq.array;
    writeln(v);
    return 0;
}

となります，v -> sort -> uniqと，自然な順番(感想には個人差があります)でソースコードが書けているのがわかるでしょうか。

このように，UFCSを使うと，ソースコードを自然に書け，メソッドチェーンと呼ばれる記法が実現できます。

プロトタイプ宣言がいらない

プロトタイプ宣言がいりません，後方の関数も参照可能です。

import std.stdio;

int collatz(int i) {
    if (i == 1) return 0;
    if (i % 2 == 0) return 1 + even(i);
    else return 1 + odd(i);
}

int even(int i) {
    return collatz(i / 2);
}

int odd(int i) {
    return collatz(i * 3 + 1);
}

int main() {
    writeln(collatz(100));
    return 0;
}

このように，互いに参照し合う再帰関数もプロトタイプ宣言無しで書くことが出来ます。 (ちなみに，このコードは何をしているコードでしょうか？)

細かいの

// void mainと書けます(return 0がいらなくなります)
void main() {
    int sm = 0;
    // rep(i, n)はいらないです
    foreach (i; 0..10) {
        sm += i;
    }
    assert(sm == 45);
    sm = 0;
    // 逆順もできます
    foreach_reverse (i; 0..10) {
        sm += i;
    }
    assert(sm == 45);

    // longは必ず8byteです，typedef long long llとはオサラバ
    assert(long.sizeof == 8);

    assert(2 ^^ 4 == 16); // 累乗演算子があります
    assert(10 ^^ 9 + 7 == 1_000_000_007);


    long f(int x) { // 関数の中に関数が書けます，再帰関数も書けます
        if (x <= 1) return 1L;
        return f(x-2) + f(x-1);
    }
    assert(f(0) == 1 && f(1) == 1 && f(2) == 2 && f(3) == 3 && f(4) == 5);
}