D言語で競技プログラミングをやっていく

20073 ワード
競技プログラミング dlang dlang テキストリンク

最近ずっと時間の許す限りAtCoderの過去問やプロジェクトオイラーをやってます。メインで使っている言語はRubyなのですが、速度的にLL言語だと間に合わないときでもD言語なら行けるんじゃないかと思ってます。（とは言え競プロは正しいアルゴリズムを使えばRubyでも突破できることも多い？これは未検証...）

というわけでD言語使ったテンプレ的なものを紹介してみたいと思います。

ちなみに自分がD言語を使う理由：

  • 速そう
  • map/reduceなどの高階関数が使えそう　←　ここ
  • (コンパイル言語 ∧ AtCoderで選択できる) 言語の中ではメジャーで枯れてる

Rust使ってみたいけどわかりません

参考にしたサイト

基本

デバッグ用文字列と標準入力の切り替え

  • ヒアドキュメントの部分をコメントアウトしたりしなかったりすれば、その先のコードは自由に組み替えられます
import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;

//string lines = q"[
//abcdeffg]";

void main()
{

  string lines;
  string buf;

  while (!stdin.eof) {
    buf = stdin.readln();
    lines ~= buf;
  }

  string[] array = splitLines(lines);
  writeln(to!string(array));
}

連番作成・結合して文字列化

Rubyだと、 (0..5).to_a で終わるところではある。

import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;

import std.range : iota;
import std.array;

void main()
{
    int[] array = iota(0, 5).array;
    assert([0, 1, 2, 3, 4] == array);

    // 最初こうかな？と思ったけど
    // writeln(array.map!(s => s.to!string).join(","));
    // ---
    // 上の書き方は Rubyで言うなら map{|s| s.to_s}.join(",")

    // コメントの書き方であれば
    array.map!(to!string).join(",").writeln;
    // ---
    // Rubyであれば下記のような感じか？
    // puts array.map(&:to_s).join(",")
}

巨大な数・INF

import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;

int INF = 1<<25;

void main()
{
  writeln(INF);
}

複数要素を一度に設定

readInts, readInt, readLongs, readLong

  • 標準入力をうまいことintやlongの配列にするコードです
import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;

import std.array;

// STDINから数値を読み取ってintの配列にする
auto readInts() {
  return array(map!(to!int)(readln().strip().split()));
}
// STDINから数値を読み取ってintの配列の最初だけとる
auto readInt() {
  return readInts()[0];
}
// STDINから数値を読み取ってlongの配列にする
auto readLongs() {
  return array(map!(to!long)(readln().strip().split()));
}
// STDINから数値を読み取ってlongの配列の最初だけとる
auto readLong() {
  return readLongs()[0];
}

// 以下のようなファイルを作って
// 標準入力にしてバイナリに食わせるとテストできる。
// 一回のreadInt()で１行だけ取得できるはず
// -----------------------------------------------
// $ cat ints.txt
// 1 2
// 2 3
// 4 5
// -----------------------------------------------
// $ dmd read_nu.d && cat ints.txt | ./read_nu
// [1, 2]
// [2, 3]
// [4, 5]
void main() {
  for (int i = 0; i < 3; i++) {
    writeln(readInts().to!string);
  }
}

readlnTo

  • こっちはもっと汎用的で、使用する型に合わせて値がセットされます
import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;

import std.array;

// STDINから数値を読み取って
// 複数ある型に合わせた配列にする
void readlnTo(T...)(ref T t) {
  auto s = readln().split();
  assert(s.length == t.length);
  foreach(ref ti; t) {
    ti = s[0].to!(typeof(ti));
    s = s[1..$];
  }
}

// 以下のようなファイルを作って
// 標準入力にしてバイナリに食わせるとテストできる。
// 一回のreadlnTo()で１行だけ取得できるはず
// 複数の引数が許容されるので、一度に複数の変数が初期化できる。
// -----------------------------------------------
// $ cat ints.txt
// 1 2 100
// 2 3 110
// 4 5 120
// -----------------------------------------------
// $ dmd readln2.d && cat readln2.txt | ./readln2
// v = 1, k = 2, w = 100
// v = 2, k = 3, w = 110
// v = 4, k = 5, w = 120
void main() {
  for (int i = 0; i < 3; i++) {
    int v,k,w;
    readlnTo(v,k,w);
    writef("v = %d, k = %d, w = %d\n", v, k, w);
  }
}

stringsTo

  • 上のやつを改造して、string型から変換していくものを作ってみた。これで動的言語にだいぶ近づいた。
import std.stdio;
import std.conv;
import std.string;
import std.format;
import std.algorithm;

void stringsTo(string, T...)(string str, ref T t) {
  auto s = str.split();
  assert(s.length == t.length);
  foreach(ref ti; t) {
    ti = s[0].to!(typeof(ti));
    s = s[1..$];
  }
}

void main()
{

  //string lines;
  //string buf;
  //
  //while (!stdin.eof) {
  //  buf = stdin.readln();
  //  lines ~= buf;
  //}

  string lines = q"[4 5
]";

  string[] array = splitLines(lines);

  int N, M;
  stringsTo(array[0], N, M);
  writef("N = %d, M = %d\n", N, M);
}

まとめ

アルゴリズムへの精進が足りないので、もうちょっと頑張っていきたいと思ってます。。。

Formula Parser式解析クラス
中国語漢字からデジタルコードへの変換方法【回転】