ABC044 B問題「美しい文字列」をD言語で解く
理由(ワケ)あって4ヶ月弱休職していましたが、今月から復帰しました。Yousackです。休んでいた間テレビを見る以外のことをほとんどしていなかったので様々なことをリハビリしています(機械学習、プログラミング、音ゲー、ダーツ、……)。
競技プログラミングもリハビリ中で、久しぶりにAtCoder Problemsの色塗りをしています。その中でD言語っぽく書けた問題があったので紹介します。
題意
文字列 w 中に現れる各文字種全てが偶数回現れているかどうかを判定する。
解法
実際に数える。
プログラム
Submission #1873792 - AtCoder Beginner Contest 044
import std.stdio, std.string, std.conv, std.range, std.algorithm; void main() { auto w = readln.chomp; int[char] char_count; foreach (c; w) { char_count[c]++; } if (char_count.values.all!"a % 2 == 0") { "Yes".writeln; } else { "No".writeln; } }
int[char] char_count
は、char
をキーとし int
を値とする連想配列 (associative array) です。 int
のデフォルト値は 0
なので今回は初期化の作業は必要ありません。宣言するだけで大丈夫です。
連想配列について:Associative Arrays - D Programming Language
型について:Types - D Programming Language
foreach
では、文字列 w
の先頭から文字 c
を1文字ずつ取り出して char_count
のキーとして突っ込み、対応する値をインクリメントしています。D言語では string
は immutable char[]
なので型推論が働くため単に c
と書くことができます。今回は必要ありませんが 、ref c
とすることで参照を取り出すことができるので、オブジェクト自身を操作することができます(今回は immutable
なので無理ですが)。
問題は各文字種全てが偶数回現れるかどうかを判定する部分です。自明ですが、現れない文字は0回出現していることと同値のため、偶数回の出現として扱うことができます。さて、D言語の連想配列には .values
というプロパティがあります。
https://dlang.org/spec/hash-map.html#properties
これはある連想配列の値を全て並べた配列です(同様に .key
もあります)。各文字種が偶数回現れたかどうかを判定したいため、今回はこの値だけ見れば良さそうです。
.values
の後には .all!"a % 2 == 0"
と続いています。 all
は std.algorithm
にいるテンプレートで、テンプレート引数には真偽値を返す述語を文字列として渡します。各要素を a
に代表させて、それを2で割った余りが0になるかどうか、すなわちその数が偶数であるかどうかを判定しています。全ての要素について true
と評価できれば all
は true
を返します。
https://dlang.org/phobos/std_algorithm_searching.html#all
ちなみにここではUFCS (Uniform Function Call Syntax) という糖衣構文のようなものを使っていて、簡単に言うと function(a, b, ...)
と a.function(b, ...)
が同義になるシステムです(これは再帰的に適用できるので fa(fb(fc(x), y))
は x.fc.fb(y).fa
と書けます)。そのためこの部分は本来は all!"a % 2 == 0"(char_count.values)
と書きますが、自分はRuby出身者でメソッドチェーン大好きマンのためUFCSを多用しているので上のように書きました。ここが一番のD言語らしさだと思っています。つまり、配列・連想配列のプロパティと std.algorithm
や std.range
、 std.container
などにいる関数・テンプレートさえ覚えれば、左から右へ流れるようにメソッドチェーンを書くことができます。D言語では引数を取らない関数は括弧を省略することができるため、 上記の再帰的なUFCSの例のように書くことでタイプ数の減少・括弧の対応の複雑さの解消にもつながります。
https://dlang.org/spec/function.html#pseudo-member
最近はAtCoderではLLVMベースのコンパイラであるLDCを使って提出していますが、簡単な問題であればほぼ全てのケースで1msで通ります。みんなもD言語で競プロをやろう。