僕は競技プログラミングを始めて1年と少しになりますが、これまで問題を解くためにC++を使っていました。そして、最近D言語という言語が便利だという記事を読んで、一度触ってみたいなあと思っていたところにAtCoder Beginners Selectionという競技プログラミング入門者向けのコンテンツができたため「これはやるしかない！」と思い、D言語でこれらの問題を解いてみることにしました。
drkenさんのQiita記事「AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～」を参考に選ばれた10+1問をまとめたセットです。ここに挙げられている問題を解けば、競プロ初心者がAtCoderでコンテストに参加するために基礎的な実力がつくとされています。
この記事は、すでにC++で競技プログラミングをしていてD言語に興味がある方向けの導入記事となっています。
Yousackさんが投稿してくださったAtCoderに登録したら解くべき精選過去問10問をD言語で解いてみた - D言語の構文と標準ライブラリを使い倒す編という記事がありますので、よりD言語らしい実装についてはそちらもご参照ください。
それでは、順番に解いていきましょう
practice contestのA問題ですね。
内容としては、3つの整数a,b,cと文字列sを順番に読み込んで、a+b+cとsを順番に出力するだけの問題です。標準入出力のやり方を覚えるためにあるんだと思います。早速勉強していきましょう。
以下のソースコードは、問題文にあるお手本のコードを写経しただけのものです。
import std.stdio;
import std.string;
import std.conv;
void main(){
int a=to!int(chomp(readln()));
string[] input=split(readln());
int b=to!int(input[0]);
int c=to!int(input[1]);
string s=chomp(readln());
writefln("%d %s",a+b+c,s);
}
main関数1行目から見ていきましょう。
int a=to!int(chomp(readln()));
まずreadln()関数ですが、これは標準入力から1行読み込む関数です。改行文字を含めてstring型で読み込んでくれます。そして読み込んだ文字列から改行文字をchomp()関数で削って、to!int()関数でint型に変換しています。
string[] input=split(readln());
int b=to!int(input[0]);
int c=to!int(input[1]);
さて、次は一行に2つの整数が書かれているものを読み込んでいきます。C++では
cin>>b>>c;
と書けば一瞬で読み込めるため強いのですが、D言語はC言語から派生した言語であるためそのような機能はないみたいです。そのため、readln()関数で読み込んだものをsplit()関数で分断(chomp()は不要のようです)してinputという文字列型の配列に入れています。配列の宣言のしかたがCとは違うので注意ですね。
string s=chomp(readln());
writefln("%d %s",a+b+c,s);
文字列を読み込むのはもはや簡単ですね。文字列を読み込んだら、writefln()関数で答えを出力しています。writefln()関数のフォーマット指定子は基本的にはC言語のprintf()関数と同じものが使えるようですが、少し違うところもあるようです。競プロをするだけならそれほど気にしなくてよさそうですね。最後に改行を出力しないwritef()関数もあります。
チュートリアルを終えたところで1問目に行きましょう。
2つの正整数a,bの積が偶数か奇数かを判定する問題です。簡単ですね。さっき勉強したことを使って解いていきます。
import std.stdio;
import std.string;
import std.conv;
void main(){
string[] input=split(readln());
int a=to!int(input[0]);
int b=to!int(input[1]);
if(a*b%2)
writefln("Odd");
else
writefln("Even");
}
if文の文法はCと同じですね。この問題ではオーバーフローの心配も無く、特筆すべき点はありません。ちなみにD言語では標準ライブラリで多倍長整数が使えます（最高）。
0か1が3つ並んだものが与えられるので、1がいくつあるか答える問題です。
import std.stdio;
import std.string;
import std.conv;
void main(){
string s=readln.chomp;
int ans=0;
for(int i=0;i<3;i++)
if(s[i]=='1')
ans++;
ans.writeln;
}
入力と出力にメソッドチェーンを使ってみました。メソッドチェーンもC/C++にはない機能ですね。1問目で文字列を読み込んだときと比べてもらえば分かるのですが、引数がない場合に関数の()を省略できたり、引数が1つの場合にfunc(a)をa.funcのように書けたりします。便利なので好きです。
あとは、writefln()をwriteln()に変えました。writeln()関数は引数を自動的に文字列型に変換して出力してくれる関数です。こっちのほうが便利な気がしますね。
for文の文法はC++と同じで、文字列の各桁を見て'1'ならば答えをインクリメントしました。
Nこの整数が与えられるので、2で割れる回数が一番少ないものを探して、それが何回2で割れるかを出力します。
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
void main(){
int N=readln.chomp.to!int;
string[] input=readln.split;
int ans=100;
for(int i=0;i<N;i++){
int A=input[i].to!int;
int count=0;
while(A%2==0){
count++;
A/=2;
}
ans=min(ans,count);
}
ans.writeln;
}
while文を使ってみました。文法は例によってCと同じです。助かります。あとは、std.algorithmをimportして、min()関数を使ってみました。アルゴリズム自体の解説はなくてよいと思います。
500円玉をA枚、100円玉をB枚、50円玉をC枚持っているので、合計金額をX円にする方法が何通りあるかを調べます。
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
void main(){
int A=readln.chomp.to!int;
int B=readln.chomp.to!int;
int C=readln.chomp.to!int;
int X=readln.chomp.to!int;
int ans=0;
for(int i=0;i<=A;i++)
for(int j=0;j<=B;j++)
for(int k=0;k<=C;k++)
if(i*500+j*100+k*50==X)
ans++;
ans.writeln;
}
実 質 C ＋ ＋
計算量も気にしなくてよいので楽勝ですね。
1からNまでの整数で、10進法での各桁の和がA以上B以下であるものの総和を求めます。
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
void main(){
int ans=0;
string[] input=readln.split;
int N=input[0].to!int;
int A=input[1].to!int;
int B=input[2].to!int;
for(int i=1;i<=N;i++){
int sum=digit_sum(i);
if(A<=sum && sum>=B)
ans+=i;
}
ans.writeln;
}
int digit_sum(int N){
int ret=0;
string S=N.to!string;
for(int i=0;i<S.length;i++){
ret+=S[i]-'0';
}
return ret;
}
関数宣言をしてみました。D言語ではプロトタイプ宣言が不要ということで、digit_sum関数をあえてmain関数より後ろに書いてみましたが全然OKマルという感じでした。to!string関数を使ってみたりS.lengthで文字列の長さを取得してみたりしましたが、これも実質C++と言っていいと思います。移行がすごくやりやすくて本当に助かります。
N枚のカードをAliceとBobが順番に1枚ずつ取っていって、2人が得点を最大化するように動いたとき、Aliceの取ったカードの合計がBobのそれよりもいくつ多くなるかを出力します。
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
void main(){
int N=readln.chomp.to!int;
string[] input=readln.split;
int[] a;
for(int i=0;i<N;i++)
a~=input[i].to!int;
sort!("a>b")(a);
int Alice=0,Bob=0;
for(int i=0;i<N;i++){
if(i%2)
Bob+=a[i];
else
Alice+=a[i];
}
(Alice-Bob).writeln;
}
問題自体はとても簡単で、与えられた数列を降順でソートして前から順にとっていくだけでよいのですが、C++と違う点がいくつか出てきていますね。
1つめは配列です。C++ならvector<int>を使いたいところですが、D言語にはvectorはありません。しかし、配列がvectorのような役割もできるようになっています。
int[] a;
で空の配列を宣言し
a~=x;
で要素xを追加できます。それぞれC++でいうところの
vector<int> a;
a.push_back(x);
に対応していると考えてよいのではないでしょうか。
ソートの方法も少し特殊です。基本的には
sort(a);
のような書き方でよいのですが、今回は降順ソートしたいので、述語（ソート基準）を指定しなくてはいけません。その指定方法は、第一引数をa,第二引数をbとして
sort!("a>b")(a);
のようにします（詳しくはこちらを参考にしてください）。
さまざまな大きさの餅が与えられるので、最大で何段の鏡餅を作れるのかを調べます。
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
void main(){
int N=readln.chomp.to!int;
bool[int] set;
for(int i=0;i<N;i++){
int d=readln.chomp.to!int;
set[d]=1;
}
set.length.writeln;
}
何種類の整数が出てくるかを数えればよいのでsetを使いたいところですが、D言語にはsetはありません。代わりに連想配列が使えます。連想配列は
ValueType[KeyType] AA;
の形で宣言することで利用でき、C++のmapのように
AA[key]=value;
の形で要素を追加できます。要素数はAA.lengthで得られます。
10000円札、5000円札、1000円札を合計N枚使ってY円を作れるか判定します。
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
void main(){
string[] input=readln.split;
int N=input[0].to!int;
int Y=input[1].to!int;
for(int i=0;i<=2000;i++){
for(int j=0;j<=2000;j++){
if(i+j>N)
continue;
if(i*10000+j*5000+(N-(i+j))*1000==Y){
writeln(i," ",j," ",N-(i+j));
return;
}
}
}
writeln("-1 -1 -1");
}
計算量を気にしなくてはいけない問題ですが、特筆すべき点は特にありません。サクっとO(N^2)で解いてしまいましょう。
与えられた文字列Sが、「dream」「dreamer」「erase」「eraser」のみからできているか調べます。
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
void main(){
string[] T=["maerd","remaerd","esare","resare"];
string S=readln.chomp;
char[] U=S.dup;
reverse(U);
S=U.dup;
while(S.length){
string V=S.dup;
for(int i=0;i<4;i++){
if(S.length<T[i].length)
continue;
if(S[0..T[i].length]==T[i]){
S=S[T[i].length..$];
break;
}
}
if(V.length==S.length){
writeln("NO");
return;
}
}
writeln("YES");
}
逆順から見ると解けます。
ここでは、文字列の反転と切り出しをしました。D言語でのstringはimmutable(char)[]という変更不能なchar配列の別名であるので、reverse()関数による反転ができません。よってdupで一旦通常のchar配列にコピーしてから反転して戻しています。
また、文字列Sに対して
S[a..b];
でS[a]からS[b-1]までの部分文字列を参照可能です（文字列以外の配列に対してもこの操作が可能です）。ここで、$は配列の長さを表していて、たとえばS[a..$]のようにすればS[a]以降をすべて切り出すことができます。
点(0,0)から1秒に上下左右に1マスずつ動けるAtCodeerくんが、決められた時刻に決められた点に存在可能かどうかを判定します。
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.math;
void main(){
int N=readln.chomp.to!int;
int t=0,x=0,y=0;
for(int i=0;i<N;i++){
string[] input=readln.split;
int T=input[0].to!int;
int X=input[1].to!int;
int Y=input[2].to!int;
if(abs(X-x)+abs(Y-y)>T || (abs(T-t)%2)!=((abs(X-x)+abs(Y-y))%2)){
writeln("No");
return;
}
t=T,x=X,y=Y;
}
writeln("Yes");
}
絶対値を求めるabs関数を使用するためにstd.mathをimportしました。それ以外に特筆すべき点はありません。
いかがでしたでしょうか？これでD言語でAtCoderにチャレンジする土台が整ったと言えるのではないでしょうか。僕もD言語はほぼ初心者なので、勉強しながら書いてみました。至らぬ点だらけだとは思いますが、少しでも参考になれば幸いです。ミスの指摘、アドバイス等あればTwitterまでリプライもしくはDM、もしくはメール（takeo1116hp@gmail.com）をお願いします。