cafelier@SRM

競技プログラミングのためのD言語 (1/2)

03:22 |

AtCoder で使える、 Google Code Jam 2012 予選 でもトップの人が宣伝している、などなどの理由で最近D言語が競技プログラマーの間でブームらしいです。SPOJやCodeChefでもリストには入っていますがバージョン古い気がするので微妙です。このビッグウェーブに乗るべくD言語を使ってみようかなーという人向けの紹介記事を書きます。

• 標準ライブラリでできる範囲のことだけ書きます（多くのオンラインジャッジがそうなので）。
• C か C++ か Java か C# での競技プログラミング経験があった方が読みやすいと思います。
• Dならではの超絶技巧アルゴリズムコードみたいな話はしません。
• Dならではの魅力が云々みたいな話もしません。
• 普通の競技プログラミングのごく普通のコードをDで書くための手引書です。
• 魅力が云々は使ってれば体でわかるだろ！と思っています。

まずは、(1/2) では、これだけ知っておけば、競技プログラミングの最中に何かがD言語で書けなくて問題が解けないということはないだろう という知識の部分だけ書きます。別の言い方をすると、「Codeforces の Unknown Language Round でD言語が出たらこのページを見れば最初の5問は瞬殺」が目標です。

基本情報

言語やライブラリの仕様は http://dlang.org/ に書いてあります。

日本語訳は http://www.kmonos.net/alang/d/ にありますが１年分古いです（すみません）。基本的には日本語訳でもまだほとんど問題ないはずですが、「あれ？書いてあることと動作が違うぞ？」と思ったときは本家の英語の方を必ず確認してください。

日本でD言語を活発に使っている人たちはよくTwitterで見かけます。「D言語」という単語や #d_lang というハッシュタグを含むツイートをしていると @repeatedly さんや @mono_shoo さんに発見されてレスがつく可能性があるので積極的に絡んでいくと色々Dの情報が得られるかも知れません。

• Google Code Jam 2012 の D言語での解答例
• Google Code Jam 2011 の D言語での解答例
• Google Code Jam 2010 の D言語での解答例
• Google Code Jam 2009 の D言語での解答例
• Google Code Jam 2008 の D言語での解答例

インストール＆使い方

コマンドラインでの使い方だけ書きます。GUI や IDE がないとわからない！という人は…頑張って他の解説を探してください。

• コンパイラは http://dlang.org/download.html からダウンロードできます。
  • dmd.2.xxx.zip を展開すると dmd2/windows/bin や dmd2/linux/bin に各OS用のコンパイラが入ってます。好きなようにパスを通して使って下さい。
  • あるいは、Windows なら dmd Windows installer を実行するとパス通すまで勝手にやります。

D言語のソースコードは .d という拡張子のファイルに書きます。hogehode.d に書いたコードをコンパイルするには

dmd hogehoge.d

です。hogehoge.exe (Windowsの場合) か hogehoge (Linux等の場合) というバイナリができるので動かしてください。

rdmd hogehoge.d

とするとコンパイル＆実行を一発でやってくれるので便利です。最近私はこれしか使ってません

文字コード

ソースファイルの文字コードはUTF-8かUTF-16かUTF-32のどれかです。日本語のコメントを書くときは、Shift_JISやEUC-JPで保存しないように気をつけてください。日本語コメント書かない場合は気にしなくていいです。

基本的な構造

プログラムは void main() という関数から実行されます。if や for や while や do-while や continue や break や switch や goto や return の使い方は全部 C++ や Java と同じです。関数の定義の仕方も同じです。コメントの書き方も同じです。全部同じです。同じように使ってください。

void main()
{
   // 100以下の素数の和を計算している。
   int total = 0;
   for(int n=2; n<=100; ++n) {
      if( is_prime(n) )
         total += n;
   }
}

/* 素数判定 */
bool is_prime(int n)
{
   for(int v=2; v*v<=n; ++v)
      if( n%v == 0 )
         return false;
   return true;
}

CやC++と違って、関数はどの順番に並べても構いません。C言語の「プロトタイプ宣言」みたいなものはありませんので書かないで下さい。

詳しくはこちら

• Statement: 英語 日本語

基本的な型

これも基本的にC系の言語とおなじです。同じように使ってください。

• bool は true か false かが入る
• char は 8bit
• short は 16bit 整数
• int は 32bit 整数
• long は 64bit 整数
• uint は符号なし32bit 整数
• ulong は符号なし64bit 整数
• float は 32bit 実数
• double は 64bit 実数
• real はIntelのx86 CPUなら80bit 実数

使える演算子も全部同じです。+, -, *, /, %, ビット演算, 等号不等号各種, += で加算代入, ++ でインクリメント, などなど。同じように使ってください。

詳しくはこちら

• Type: 英語 日本語
• Expression: 英語 日本語

標準出力

C の printf や C++ の cout や Java の System.out に相当するものは、標準ライブラリの std.stdio モジュールを import して使います。

import std.stdio;

void main()
{
   write("Hello, ");  // write は改行なしで出力
   writeln("world."); // writeln は最後に改行をつける

   writeln(1+2*3); // 文字列以外のものを渡したら自動で文字列化して表示
   writeln(1, " ", 10, " ", 3.141592); // 引数を複数渡すとつなげて表示
}

こんな風に出力されます。

Hello, world.
7
1 10 3.141592

細かい書式などの指定は、write, writeln の代わりに writef と writefln を使います。

import std.stdio;

void main()
{
   writef("%d %x %b ", 17, 17, 17); // 10進, 16進, 2進
   writefln("%.2f", 3.141592); // 小数点以下2桁まで
}

17 11 10001 3.14

詳しくはこちら

• std.stdio: 英語 日本語
• フォーマット指定: 英語 日本語

標準エラー出力

デバッグ用の出力を C++ なら cerr、Java なら System.err に出すことがあると思いますが、D だと、stderr の write, writeln, writef, writefln を使います。

import std.stdio;

void main()
{
   stderr.write("Hello, ");
   stderr.writeln(1+2*3);
   stderr.writef("%d %x %b ", 17, 17, 17);
   stderr.writefln("%.2f", 3.141592);
}

普通の標準出力の方も、これに揃えて stdout.writeln("Hello") みたいな書き方もできます。

詳しくはこちら

• std.stdio: 英語 日本語
• フォーマット指定: 英語 日本語

標準入力

データを標準入力から読み込むには、やはり同じく std.stdio の、readf （C言語のscanfっぽい書式指定読み込み）と readln （一行読み込み）という関数があります。stdin.readf や stdin.readln と書いても同じ機能です。ただし、readf は scanf 等に似て非なるものなので、慣れずに使うとハマります。ハマりポイントの説明が面倒なので、readln だけを使うのが競技プログラミングには個人的にはおすすめです。

import std.stdio;

void main()
{
   for(int i=0; i<100; ++i) {
      string s = readln(); // 一行読み込み
      write(s);
   }
}

readln() は標準入力から一行読み込みます。注意点として、C++ の std::getline と違って、readln は最後に改行文字を含みます。要らない場合は、std.string モジュールの chomp() 関数を使うと、末尾の改行文字がもしあれば落としてくれます。

import std.stdio;
import std.string;

void main()
{
   string no_kaigyo_firstline = chomp(readln());
}

標準入力の終わり (EOF) では、改行文字を含まない、つまり長さ 0 の文字列が帰ってくるので、EOF判定はそれでやるか、stdin.eof() で判定します。

import std.stdio;

void main()
{
   string s;
   while( (s=readln()).length == 0 )
      writeln("<", chomp(s), ">");
   // あるいは
   // for(;;) {
   //    string s=readln();
   //    if( stdin.eof() ) break;
   //    writeln("<", chomp(s), ">");
   // }
}

競技プログラミングの場合、入力データはほぼ確実に空白区切りで渡されるので、そういう入力形式のときは、std.array の split 関数で切り分けてから、std.conv の to!int 関数などで文字列から変換します。

例えば、かの有名な A+B Problem はこんなコードになります。

import std.stdio; // readln
import std.array; // split
import std.conv; // to

void main()
{
   string[] input = split(readln()); // splitで文字列を文字列の配列に切り分け
   int a = to!int(input[0]); // 第0要素を整数に変換
   int b = to!int(input[1]); // 第1要素を整数に変換
   writeln(a+b); // 表示
}

splitは前後の空白等を自動で削ってくれるので、chompなくてもいいです。予想が付くとおもいますが、doubleに変換したいときはto!doubleです。readln() と split() と to!int と to!long と to!double さえあれば基本的に困らないはず。

詳しくはこちら

• std.stdio: 英語 日本語
• std.array: 英語 日本語
• std.conv: 英語 日本語
• std.string: 英語 日本語

データ構造：配列

配列を使う適当なサンプルプログラムです。エラトステネスの篩というアルゴリズムです。

import std.stdio;

void main()
{
   int N = 1000;
   bool[] is_prime = new bool[N]; // 長さNの配列
   int[] primes; // 長さ0の空配列
   for(int p=2; p<N; ++p) {
      if( is_prime[p] ) { // 添え字アクセス
         primes ~= p; // 配列の末尾に追加（push_back）
         for(int q=p+p; q<N; q+=p)
            is_prime[q] = false; // 添え字アクセス
      }
   }
   writeln( primes.length ); // 1000未満の素数は何個？
}

型 T の要素の配列は T[] という型です。配列を新しく作るときは new T[要素数] です。Javaと同じですね。new してますが、ガベージコレクションが働いて要らなくなったらメモリは勝手に解放されるので、解放のことは気にしなくていいです。

Java と違うのは、途中で配列の長さを変えられます。~= 演算子で末尾に要素を足します。ArrayList や std::vector に近いです。.length で長さがとれます。

別のサンプル。

import std.stdio;

void main()
{
   int[] fractal = [0];
   for(int i=1; i<10; ++i)
      fractal = fractal ~ [i] ~ fractal; // ~ は配列結合演算子
   fractal.length = 30; // .lengthは代入して変更もできます。std::vectorでいうresize()です。
   writeln(fractal);
}

[0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1]

別の。

void main()
{
   int[] primes = [2, 3, 5, 7, 11, 13, 17];
   writeln( primes[0..1] ); // [2]
   writeln( primes[0..2] ); // [2, 3]
   writeln( primes[2..$] ); // [5, 7, 11, 13, 17]
   writeln( primes[2..$-1] ); // [5, 7, 11, 13]
}

配列[x..y] でx番目(含む)からy番目(含まない)の部分配列が取り出せます。O(1)です（単にポインタずらしているだけなので）。配列の添え字の中だけで使える $ という特殊な式があって、その配列の .length を指します。

別のサンプル。一括処理みたいなの。

int[] x = [1,2,3];
int[] y = [4,5,6];
int[] z;
z[] = x[] + y[]; // [5,7,9];
x[] = z[] + 3; // [8,10,12];
x[] = 1; // [1,1,1]

別の。今ではこの組み込みのsortは使わない（次回説明します）のですが、とりあえず今回の範囲で競技プログラミングに必要な要素に全部触れておこうと思ったのでとりあえずのソートの仕方にも触れておきます。詳しくは次回。

int[] x = [111,2,33];
x.sort;
// x は [2,33,111] になる。

もう一つだけ。

int[] x = [1,2,3];
int[] y = x.dup; // コピー！
y[0] = 100;
writeln(x[0]); // 1

.dupで配列のコピーを作ります。単にy=xとすると同じ領域を指すのでyを書き換えたらxも変わります。

詳しくはこちら

• Arrays: 英語 日本語
• Simd: 英語

データ構造：文字列

すでに何度か出てきてますが、string という型が文字列です。

void main()
{
   string hello = "hello";
   for(int i=0; i<hello.length; ++i)
      writeln(hello[i]);
}

h
e
l
l
o

string の実体は immutable(char)[ ] という型で、つまりだいたい char の配列です。なので、~ で結合できますし、[ ] で添字アクセスできますし、[1..$-1] で部分文字列を作れます。ただし、immutable つまり 変更できない char の配列なので、

hello[0] = 'w';

のようなコードはコンパイルエラーになります。書き換えはできません。（JavaのStringと同じです。）書き換えがしたいときは char[] を別途つくってください。

文字列としての色々な便利操作関数は以下のモジュールにあります。

• std.string: 英語 日本語
• std.regex: 英語 日本語 （正規表現: std.regexp は古いので std.regex を使います。）

そのほか競技に使う標準モジュール

• core.bitop: 英語 日本語
  • ビット演算です。bsf() と popcnt() は競技プログラミングでたまに便利です。
• std.math: 英語 日本語
  • 数学関数です。sin() とか log() とか。まあ普通です。
• std.mathspecial: 英語 日本語
  • 数学関数その２です。ガンマ関数とかはこっちですが競技プログラミングではあまり使わないかも。
• std.numeric: 英語 日本語
  • gcd と FFT があります。
• std.random: 英語 日本語
  • 乱数です。

中間まとめ

「UnknownLanguageRound最初の数問は瞬殺」編をお届けしました。準備段階なので、これだけだと特にD言語が魅力的には見えないかもしれませんが、その辺は続きをご覧下さい…と言いたいところですが、実は私にとって、こと競技プログラミングに限って言うと、D言語の一番の魅力はもうここまで紹介済みです。つまり

　　Dの配列はstd::vectorよりJavaの配列よりJavaのArrayListよりC#のArrayListより使いやすい

と思うのです。（C#の多次元配列は羨ましいのでここには列挙しない）。文章で読んでるだけだとなかなか実感が湧かないかもしれませんが、配列のスライス（部分配列取り出し）と結合とその他色々はとても便利です。RubyやPythonを使っている人にはその辺の機能は当たり前だと思いますが、その当たり前の機能が、C++に匹敵する速度で手に入るのは非常に魅力的です。言語の定数倍の遅さのせいで正しいはずのコードが通らない、ということはDならまずありません。

競技プログラミングのためのD言語 (2/2)

03:22 |

続きです。

foreach文

string[] strs = ["aaa", "bbb", "ccc"];

foreach(s; strs) // strsの要素をループ
   writeln(s);
foreach(i, s; strs) // strsの要素を添え字付きでループ
   writeln(i, ": ", s);
foreach(i; 0..100) // 0から99まで(100は含まない)ループ
   writeln(i);

foreach_reverse(s; strs) // strsの要素を逆順にループ
   writeln(s);
foreach_reverse(i, s; strs) // strsの要素を添え字付きで逆順にループ
   writeln(i, ": ", s);
foreach_reverse(i; 0..100) // 99から0までループ
   writeln(i);

はい。

基本的ではない型・演算

標準ライブラリの std.bigint というモジュールを import すると BigInt 型が使えます。普通に+-*/で演算できます。JavaのprobablePrimeのような格好いいメソッドはありません。

import std.stdio;
import std.bigint;

BigInt factorial(int n) {
   return n>0 ? factorial(n-1) * n : BigInt(1);
}

void main()
{
   writeln(factorial(1000));
}

複素数が言語組み込みの型としてあります。cfloat, cdouble, creal という型名です。std.complexというライブラリ実装に置き換えるという話があったんですがまだ置き換わってないので組み込み型の方を紹介します。

import std.stdio;
import std.math; // 実部 .re と虚部 .im と四則演算以外の関数は std.math で
void main()
{
   creal z = 1+2i;
   z = z*z; // (1+2i)(1+2i) = -3+4i
   writeln(z.re); // -3
   writeln(z.im); // 4
   writeln(conj(z)); // -3+-4i
}

普通の整数や浮動小数点数にもちょっと便利機能があります。

void main()
{
   int x = 3^^4; // 3の4乗 : 81
   int veryLarge = int.max; // intに入る最大値すなわち2147483647
   real inf = real.inf; // IEEE754の∞値
}

競技プログラミング的に言うと、べき乗は3状態あるもののビットじゃないけどビットマスク、っぽいものの計算が楽になったりします。.max や .min や .inf は変数の初期値として埋めておくと役に立つ場面が色々。

詳しくはこちら

• Type: 英語 日本語
• Property: 英語 日本語
• Expression: 英語 日本語
• std.bigint: 英語 日本語
• std.math: 英語 日本語

データ構造：連想配列

std::map<string, int> や java.util.HashMap<String, Integer> のような、あれです。メモ化に使います。

int[string] m;
m["one"] = 1;
m["two"] = 2;
m["three"] = 3;
if( "four" in m ) writeln("hogehoge");
m.remove("three");
writeln(m.length); // 2
foreach(key, value; m)
   { ... }
int[string] point_to_same_as_m = m; // 同じmapを参照
int[string] another = m.dup; // コピーはdupで

そんな感じで ValueType[KeyType] という型として言語組み込みでこの機能を持っています。実装はハッシュ表を使っているので、C++のstd::mapやjavaのTreeMapのような、キーの順序通りに取り出す機能は、この連想配列にはありません。

HashSet相当のものはないので、私は bool[Type] を set としてよく使っています。

詳しくはこちら

Associative Arrays: 英語 日本語

データ構造：その他

std.container

に、BinaryHeap (priority_queue/PriorityQueue) と RedBlackTree (set/TreeSet) があります。私使ったことないので詳しくは知りません...。

詳しくはこちら

std.container: 英語 日本語

データ構造：pair, tuple

std.typecons モジュールに、Tuple!() というテンプレートが用意されています。2つ組や3つ組を作れます。

import std.typecons;

void main()
{
  Tuple!(int, string, real) t = tuple(1, "hello", 3.14); // tuple() 関数はC++のmake_pairみたいなもの、型を省略して構築
  int x = t[0]; // 0番目はint
  string y = t[1]; // 1番目はstring
  t[2] = 2.72; // 2番目はreal
}

DのTupleの良いところは、メンバの名前をfirstやsecondじゃなくて自由に決められるところです。

Tuple!(int, "src", int, "dest") edge = tuple(0, 2);
writeln(edge.src, "-->" edge.dest);

型名が長いなーと思ったら、aliasを使います（C++で言うtypedefです）。

alias Tuple!(real, "x", real, "y", real, "r") Circle;
Circle c = Circle(0.1, 0.2, 0.3);
c.r = 0.4;

詳しくはこちら

std.typecons: 英語 日本語

クラスの書き方・使い方

Tupleでメンバの名前がつけられるとなると、競技プログラミングレベルではclassやstructを定義せずに全部Tupleで済ませてしまうことがかなり多くなるのですが、必要ならばもちろんクラスを作って使うこともできます。クラスの定義、使い方はJavaと同じです。 唯一の注意点としては、コンストラクタの名前は クラス名() ではなく、this() です。あとデフォルトは public です。

詳しくは他のもっと真っ当な解説などを。

無名関数・クロージャ

void sort(int[] arr,  bool delegate(int x, int y) ordered) {
   foreach(i; 0..arr.length)
      foreach(j; i+1..arr.length)
         if( !ordered(i, j) )
            {int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp;}
}

void main() {
   int[] weight = [9,3,4,7,1,6,2,8,5];
   int[] arr = [0,1,2,3,4,5,6,7,8];
   sort( arr, (int x, int y){ return weight[x]<weight[y]; } );
}

(int x, int y){ return weight[x]<weight[y]; } の部分が無名の関数です。周りの環境のweightという変数を使うこともできています。この無名関数を変数で受けるには、<b>delegate という型で受けます。構文は上の例のような感じ。

アルゴリズム

C++の<algorithm>ヘッダに相当する物は、Dでは std.algorithm モジュールです。std.range も見ておくと便利です（特に、二分探索系の機能はstd.rangeにあります）。機能としては基本的に <algorithm> をなぞったものが多いですが、よく見るとBoyerMooreとかlevenshteinDistanceなどが紛れ込んでいてちょっと楽しいです。

楽しいかどうかはさておき、std.algorithm を使うにあたって重要なポイントは、Range という概念です。C++ では iterator というものの上にSTLのアルゴリズムがすべて組まれていましたが、D言語では Range の上に全部のアルゴリズムが組まれています。

なにやら難しそうですが、要はぶっちゃけると Range は iterator の begin と end の組と思って下さい。Topcoderなどでも

#define ALL(c) (c).begin(), (c).end()

というけしからんマクロを書いている人をよく見ますが、確かに、この二つは常に組であつかった方が色々と便利なのです。

import std.algorithm;
import std.stdio;

void main()
{
   int[] arr = [1,2,3];
   auto r = find(arr, 2);
   writeln(r); // [2,3]
}

[1,2,3] から 2 を探すと、最初に 2 が現れた位置より後ろ全体を指すRangeが返ります。別の例。count。

import std.algorithm;
import std.stdio;

void main()
{
   int[] arr = [1,2,3];
   writeln( count!((int x){return x>=2;})(arr) ); // 2以上のものの個数。2個。
   writeln( count!("a>=2")(arr) ); // 同じ意味
}

関数を引数にとるタイプのアルゴリズムの場合、アルゴリズム名!(ここ)(range) に関数を渡します。周りの環境の変数をみないのであれば、"a"を引数と思った関数のbodyの文字列を書いても行けたりします。!() は C++ でいうテンプレート引数を渡している部分になります。

普通の配列を操作する＆走査するRangeは要するにただの部分配列ですが、Rangeという概念自体はもっと抽象的なものなので

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

void main()
{
   string[] names = ["taro", "hanako", "toastman"];
   int[] ratings = [3000, 4500, 4000];

   sort( zip(ratings, names) );

   writeln(names);  // ["taro", "toastman", "hanako"]
   writeln(ratings); // [3000, 4000, 4500]
}

二つの配列を並行して走るRangeをzipでその場で作ってそのRangeをsort、とやると元の二つの配列がpairとしての順序でsortされたりします。これは割と経験的に便利です。

別の例。二分探索。

import std.array;
import std.range;

void main()
{
   int[] arr = [1,2,3,4,5];
   auto sorted = assumeSorted(arr);

   int[] lw = array(sorted.lowerBound(3)); // [1,2];
   int[] up = array(sorted.upperBound(3)); // [4,5];
}

Rangeを返値として返す関数の結果は大抵よくわからない謎の型になっていますが、auto で自動的に適切な型で受け取ることができます。あと、そのRangeをこれ以上他のアルゴリズムに渡したりしないので普通の配列にしてください、と思ったらstd.arrayのarray()関数でRangeを何でも配列化できます。

詳しくはこちら

• std.algorithm: 英語 日本語
• std.range: 英語 日本語

スレッド

std.concurrencyのspawnという関数でスレッドを起動してsendとreceiveでやりとりします。最近のマシンは4コアや8コアは持っていたりするので、ローカルで実行する形式のコンテストでは、単純にテストケースを別スレッドで並行に実行するだけで8倍の高速化が達成できたりすることがあります。

import std.stdio;
import std.concurrency;

void compute_square(Tid parent, int n)
{
   send(parent, n, n*n);
}

void main()
{
   // 100個スレッド起動
   foreach(i; 0..100)
      spawn(&compute_square, thisTid, i);

   // 100個返事が来るのを待つ
   int[] results = new int[100];
   foreach(_; 0..100)
      receive( (int i, int result)
      {
         results[i] = result;
      });

   writeln(results);
}

スレッドを起動したりメッセージ通信したりするコードはこれだけです。

詳しくはこちら

• std.concurrentcy: 英語
• std.parallelism: 英語

そして最近はstd.parallelismなどという物もできていました…知らなかった…

まとめ

とりあえず、以上です。

D言語の言語機能の紹介としては、テンプレートとかテンプレートとかテンプレートとか契約とか契約とか契約とか特徴的な部分をごっそり省いているのですが、競技プログラミングでそこまで激しくその辺りの機能を使うことはなかろうということで省いています。「○○と同じです」で済ませた部分も本当は全然同じではなくて、同じ書き方をしたらだいたい同じに動くというだけで、同じでない書き方も色々できて面白いのですが、その辺りは他のまともな解説記事を読んでみてください。ではでは。