矮小

井の中の蛙

AtCoderに登録したら解くべき精選過去問10問をD言語で解いてみた - D言語の構文と標準ライブラリを使い倒す編

をやろうとしたら先を越されていました。

が、せっかくなので競技プログラミングのリハビリをするために10問全部D言語で解いてみました。解き方は

でも解説されているので、ここではD言語らしく書けたところに注目していきたいと思います。

PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）

3つの整数の合計値と与えられた文字列を出力します。

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

void main() {
  auto a = readln.chomp.to!int;
  auto bc = readln.chomp.split.map!(to!int);
  auto s = readln.chomp;

  "%d %s".writefln(a + bc[0] + bc[1], s);
}

D言語には多重代入やC++のようなストリームやは無いので、愚直に分割してインデックスでアクセスしないといけません（誰か良いやり方あったら教えてください……）。ここではUFCS (Uniform Function Call Syntax) を使っていて、どういうものかというと、任意の関数で a(b(c(d))) と d.c.b.a が等価になるという実装です。変数 bc の場合は標準入力読み込み→改行切り落とし→空白で分割→各要素を int に変換というように、左から右に流れるように読めるようになることでコードの可読性が上がります。 writefln は書式・改行付き出力です。ここでもUFCSを使っています。

また、D言語には型推論があるので、変数を宣言する時の型は auto でだいたい通ります。

冒頭の4つの標準ライブラリはそれぞれ writefln, chomp, to, map を使うためにインポートしています。標準入力から複数の数字列を読み込んで配列に変換するためにはこの4つのライブラリが必須です。

20180321 追記

行けました。D言語を知って6年ぐらいになるけど初めて知った。すごい。

ABC086A - Product

2つの整数を受け取って、その積の偶奇を判定します。

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

void main() {
  auto ab = readln.chomp.split.map!(to!int);
  if (ab[0] * ab[1] % 2 == 1)
    "Odd".writeln;
  else
    "Even".writeln;
}

ABC081A - Placing Marbles

3桁の数字を受け取って、1が何個あるかを出力します。

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

void main() {
  readln.chomp.count('1').writeln;
}

std.algorithm には count がいます。これは与えられた配列中に、与えられた要素が存在する数を返す関数です。また、D言語では string は immutable(char)[] なので "hogehoge".count('h') とすることで文字列中の特定の文字を数えることができます。ということで入力の受け取りから答えの出力まで1行で書くことができました。

ABC081B - Shift only

N個の整数が与えられ、すべての整数を2で割り切る操作が何回できるかを出力します。

import std.stdio, std.conv, std.string, std.algorithm, std.array;

void main() {
  readln;
  auto a = readln.chomp.split.map!(to!int).array;
  auto ans = 0;

  while(a.all!"a % 2 == 0") {
    a = a.map!"a / 2".array;
    ans++;
  }

  ans.writeln;
}

いつも通り整数列を受け取って配列にしますが、今回はその変数を破壊的に操作したいので、後々のために array() を使って map() を評価して型を int[] にしておきます。

std.algorithm には all というテンプレート関数がいます。これは、文字列で受け取った述語を各要素で評価して、すべて true と評価したら trueを、そうでなければ false を返す関数です（同様に any もあります）。もしすべての要素が偶数なら、すべての要素を2で割って置き換えるという操作を愚直に行います。LDCで1msで通りました。

20180321 追記

はい。D言語は上記のようにベクトル演算といって、配列のスライスを対象として各要素に演算子を適用することができます。 map を書くことに夢中ですっかり忘れていました。

ABC087B - Coins

500円玉、100円玉、50円玉がA, B, C枚与えられたとき、これらを使ってX円を作る方法が何通りあるかを出力します。

import std.stdio, std.conv, std.string, std.algorithm, std.range;

void main() {
  auto a = readInt; // 500
  auto b = readInt; // 100
  auto c = readInt; //  50
  auto x = readInt;
  auto ans = 0;

  foreach (i; iota(a + 1))
    foreach (j; iota(b + 1))
      foreach (k; iota(c + 1))
        if (i * 500 + j * 100 + k * 50 == x)
          ans++;

  ans.writeln;
}

int readInt() {
  return readln.chomp.to!int;
}

X円からの引き算や0円からの足し算でもできそうな気がしますが、3枚の枚数の最大がそれぞれ50枚なので、全探索で間に合います。 iota はPythonで言う range() のようなものです（実際にはイテレータのようなものではなく配列を返すので厳密には違いますが）。

ABC083B - Some Sums

整数Nが与えられ、10進法でのNの各桁の合計がA以上B以下である数の合計を出力します。

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

void main() {
  auto nab = readln.chomp.split.map!(to!int);
  auto ans = 0;

  foreach (n; 1 .. nab[0] + 1) {
    auto digit_sum = n.to!string.split("").map!(to!int).reduce!"a + b";
    if (nab[1] <= digit_sum && digit_sum <= nab[2])
      ans += n;
  }

  ans.writeln;
}

foreach 文の範囲にはこのように x .. y で x 以上 y 未満の範囲を取ることができます。

肝心の各桁の和を取る部分ですが、n を一旦文字列に変換→空文字列で分割することで1文字ずつの配列に変換→各要素を整数に変換→ reduce で各要素の総和を取ることで各桁の和を取ることができます。

ABC088B - Card Game for Two

AliceとBobが、整数が書かれたN枚のカードを交互に取り合って、自分が持っている整数の和を最大化しようとします。Aliceが先攻で、2人が最善手を取り続けたとき、AliceがBobを何点上回っているかを出力します。

import std.stdio, std.string, std.algorithm, std.conv, std.range;

void main() {
  auto N = readln.chomp.to!int;
  auto a = readln.chomp.split.map!(to!int).array.sort!"a > b".array;
  auto alice = 0;
  auto bob = 0;

  foreach (i, e; a) {
    if (i % 2 == 0)
      alice += e;
    else
      bob += e;
  }

  (alice - bob).writeln;
}

foreach (i, e; a) とすることで、i にはインデックスが入ってきます。Pythonの enumerate のような関数を噛まさなくていいところが良いですね（ただし a が評価済みの配列である必要があるみたいです）。

ABC085B - Kagami Mochi

X段の鏡餅とは、どの餅も下の餅よりも厳密に小さいものがX個続いたものを言います。餅が複数個与えられるので、最大何段の鏡餅を作れるかを出力します。

import std.stdio, std.string, std.conv, std.algorithm, std.range;

void main() {
  auto n = readln.chomp.to!int;
  int[] d;
  
  foreach (_; 0 .. n)
    d ~= readln.chomp.to!int;

  d.sort.uniq.array.length.writeln;
}

整数が何種類あるか良いかを数えればいいのでカウント用の連想配列を作りたくなります（D言語にはSetがありません）が、面倒なのでソートしてユニークを取った配列の length をそのまま出力します。D言語では配列の初期化時にサイズを与えなければ動的配列になるので、~= 演算子で要素を配列の後ろに追加していくことができます。

20180321 追記

赤黒木に突っ込めば勝手にユニークな配列が取れますね。情弱だった……。要はC++でいう std::map のようなものだと思ってもらえればいいと思います（C++詳しくないのでもしかしたら違うかもしれませんが）。ということで redBlackTree(d).length.writeln; が別解となります。sort.uniq する方は2msでしたが赤黒木を使うと1msになりました。オーダーがー大きな問題を解くときには効いてくるのかな？

ABC085C - Otoshidama

10000円札、5000円札、1000円札が合わせてN枚あったとき、Y円を作ることができるお札の組み合わせを1つ出力します。できなければ-1 -1 -1を出力します。

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

void main() {
  auto ny = readln.chomp.split.map!(to!int);
  solve(ny[0], ny[1]).map!(to!string).join(" ").writeln;
}

int[] solve(int n, int y) {
  foreach (i; 0 .. n + 1) // 10000
    foreach (j; 0 .. n - i + 1) { // 5000
      auto k = n - i - j; // 1000
      if (i * 10000 + j * 5000 + k * 1000 == y)
    return [i, j, k];
    }

  return [-1, -1, -1];
}

お札が3種類あるので一見3重ループに見えますが、2種類のお札の枚数が決まれば残りのお札の枚数は引き算するだけで求められるので2重ループになります。

ABC049C - 白昼夢 / Daydream

文字列Sが与えられるので、空文字列の状態からdream, erase, dreamer, eraserのどれかを足すことでSにできるかどうかを出力します。

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

void main() {
  auto s = cast(char[])readln.chomp;
  s.reverse;

  if (s.solve)
    "YES".writeln;
  else
    "NO".writeln;
}

bool solve(char[] s) {
  if (s.length == 0) return true;
  
  if (s.length >= 5 && (s[0 .. 5] == "maerd" || s[0 .. 5] == "esare"))
    return solve(s[5 .. $]);
  if (s.length >= 6 && s[0 .. 6] == "resare")
    return solve(s[6 .. $]);
  if (s.length >= 7 && s[0 .. 7] == "remaerd")
    return solve(s[7 .. $]);

  return false;
}

初めてこの問題を見た時はどう解けばいいのか困りましたが、後ろから消していけばいいという話を見てなるほどと思いました。D言語は配列のスライスを取ることができます。また、配列の [] の中に限っては $ が配列の長さを返してくれるので、それを範囲の終端に取ることで、配列の終わりまでの要素を取ることができます。最初の入力は空文字列は与えられないので、solve にやってきた文字列の長さが0なら全ての文字列を消し切ることができたということで true、dream, erase, dreamer, eraserを反対にしたもののどれかがSを逆にしたものの頭に一致すればそれを取り除いたものを solve に渡し、いずれにも当てはまらなければ false を返せばいいです。

20180322 追記

よく考えたら正規表現にかけるだけでいいですね。

import std.stdio, std.string, std.conv, std.algorithm, std.regex;

void main() {
  auto ans = readln.chomp.matchFirst("^(dream|dreamer|erase|eraser)+$");
  if (ans) "YES".writeln;
  else "NO".writeln;
}

今回は行頭から行末まで全部にマッチしてほしいのでどちらでもいいですが、std.regex には matchAll と matchFirst の2つがいるので、適宜使い分けていきましょう。公式リファレンスにもありますが、以前使われていた match は今ではdeprecatedになっています。

ちなみにこのコードは 8ms で通りました。最大ケースは100,000文字ですが余裕でしたね。他の言語でも通るのかな？

ABC086C - Traveling

時刻0には(0, 0)におり、1時刻につき2次元平面状の上下左右のいずれかに移動できるとして、時刻tに(x, y)にいることができるかどうかを判定したいです。このような組み合わせを複数与えられたときに、全ての条件を満たすことができるかどうかを判定します。

import std.stdio, std.string, std.conv, std.algorithm, std.math;

void main() {
  auto n = readln.chomp.to!int;
  auto t_before = 0;
  auto x_before = 0;
  auto y_before = 0;

  foreach (_; 0 .. n) {
    auto txy = readln.chomp.split.map!(to!int);
    auto t = txy[0];
    auto x = txy[1];
    auto y = txy[2];
    auto time = t - t_before;
    auto x_dist = abs(x - x_before);
    auto y_dist = abs(y - y_before);
    auto distance = x_dist + y_dist;

    if (distance > time || ((x_dist + y_dist) % 2 != time % 2)) {
      "No".writeln;
      return;
    } else {
      t_before = t;
      x_before = x;
      y_before = y;
    }
  }

  "Yes".writeln;
}

先達の教えの通り、2次元平面上の点(x, y)のx + yの偶奇と移動するのに必要な時刻の偶奇が一致しなければいけないという事実を利用します。上記のコードで59msで通すことができたので、必要なオーダーの割にはまあまあの速度が出ているのではないかなと思います。

まとめ

以上のように、AtCoder初心者向け精選10問を、D言語のライブラリを駆使して上手く解くことができました。問題がアルゴリズミカルになるにつれ見た目がCやC++に近づいていく感はありますが、ABCのA-B問題であればUFCSと標準ライブラリを用いてあたかもスクリプト言語のように問題を解くことができることが示せたのではないかなと思います。私の記事をきっかけにD言語で競技プログラミングを解いてみようかなと思う人が増えてくれれば幸いです。