競プロ(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
, maxElement
が 2.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 }