競プロ(AtCoder)の問題を D 言語で解くための Tips

これは Competitive Programming (2) Advent Calendar 2018 の 12 日目の記事です。

競プロの問題を D 言語で解くための Tips を集めました。
オンラインジャッジサイトによって、D 言語のコンパイラのバージョンは異なりますので、この記事では、 AtCoder での現時点(2018/12/12)のコンパイラバージョン(DMD64 v2.070.1)を想定しています。

配列の要素を一気に書き換える

a[] = 100 と書くと、配列 a の要素を全て 100 に書き換えることができます。

import std.stdio;

void main() {
    int[3] a;   // 要素は 0 で初期化されます
    writeln(a); // [0, 0, 0]
    a[] = 100;  // 全ての全てを 100 で書き換える
    writeln(a); // [100, 100, 100]
}

2 次元配列の使い方

import std.stdio;

void main() {
    auto a = new int[][](2, 3);
    writeln(a);           // [[0, 0, 0], [0, 0, 0]]
    writeln(a.length);    // 2
    writeln(a[0].length); // 3

    a[0][1] = 100;
    writeln(a); // [[0, 100, 0], [0, 0, 0]]
}

配列の最大値、最小値を求める

reduce を使います。

import std.algorithm;
import std.stdio;

void main() {
    int[] a = [3, 1, 4, 1, 5];
    writeln(a.reduce!((a, b) => min(a, b))); // 1
    writeln(a.reduce!((a, b) => max(a, b))); // 5

    // こう書くこともできます
    writeln(a.reduce!min); // 1
    writeln(a.reduce!max); // 5
}

minElement, maxElement2.072.0 から追加されましたが、AtCoderコンパイラは 2.070.0 なので残念ながら使うことは出来ません。

Set を使う

C++set クラスに相当するクラスは D 言語の標準ライブラリにはありません。代わりに連想配列を使います。

import std.stdio;

void main() {
    bool[int] set;

    foreach (x; [3, 1, 4, 1, 5, 9, 2]) {
        set[x] = true;
    }

    writeln(set.length); // 6
    writeln(1 in set ? "yes" : "no"); // yes
    writeln(set.keys); // [5, 4, 3, 2, 1, 9]
}

スタック、キューを使う

D 言語の標準ライブラリには、スタック、キューは用意されていませんが、 DList クラスがスタック、キューの代わりになります。

スタックとしての使い方:

import std.container;
import std.stdio;

void main() {
    auto stack = DList!int();
    writeln(stack.empty); // true

    // スタックにプッシュ
    stack.insertBack(10);
    // スタックの要素をピーク
    writeln(stack.back); // 10
    stack.insertBack(20);
    writeln(stack.back); // 20

    // スタックからポップ
    stack.removeBack();
    writeln(stack.back); // 10
}

キューとしての使い方:

import std.container;
import std.stdio;

void main() {
    auto queue = DList!int();
    writeln(queue.empty); // true

    // キューに値を格納する
    queue.insertBack(10);
    queue.insertBack(20);

    // キューから値を取り出す
    int x = queue.front;
    writeln(x); // 10
    queue.removeFront();
}

タプルに名前が付けられる

import std.stdio;
import std.typecons;

alias Point = Tuple!(int, "x", int, "y");

void main() {
    auto p = Point(10, 20);
    writeln(p);   // Tuple!(int, "x", int, "y")(10, 20)
    writeln(p.x); // 10
    writeln(p.y); // 20
}