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ならまずありません。