D言語でAtCoderを解きたい！

# 前置き

[D言語くん](https://tour.dlang.org/tour/ja/welcome/welcome-to-d)かわいい！D言語書かなきゃ！！

![dman.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3618312/a2f994d1-894a-c13a-d916-1d5dfffd927e.png)

この記事は[TRIAL＆RetailAI Advent Calendar 2024](https://qiita.com/advent-calendar/2024/retail-ai)7日目の記事です。
昨日は[@nakayama_ryuseiRAI](https://qiita.com/nakayama_ryuseiRAI)さんの[「LT会を企画してみた！運営のコツと学び」](https://qiita.com/nakayama_ryuseiRAI/items/79f7394f5d4c8a17d175)という記事でした。
LTのテーマがを仕事内容に限らず持ち込めるのがおもしろそうですね。次回があれば、何かネタを探して参加してみたいと思いました。社内の交流イベントを考えている方は、この記事を参考にLT会を開いてみるのはいかがでしょうか。

さて、本日は「D言語でAtCoderを解きたい！」ということで、D言語のインストール方法と問題を解くために最初に必要となる文法を紹介しようと思います。

# D言語をインストールする

D言語は2001年に作られた言語です。C言語の後継を目指して作られた側面があるらしく、文法がかなりCに似ています。C、C++やJavaを書いた経験のある方なら容易に習得できそうです。
Dは手続き型、オブジェクト指向、関数型に対応しており、好みのパラダイムで記述することができます。

さっそくコンパイラをインストールしていきましょう。下記のページの通りにやればインストールできますが、Homebrewでもインストールできるようですので、Homebrewを使った方法を紹介します。

https://tour.dlang.org/tour/ja/welcome/install-d-locally

コンパイラが複数あって迷いますが、大体DMDで問題ありません。
M1 Mac以上(?)だとHomebrewのDMDが対応していないっぽいので、その場合はLDCをインストールしましょう。
```zsh
brew install dmd

# ldcの場合。ldc"2"なのに注意
# brew install ldc2
```
インストールできたら以下を`hello.d`としてファイル作成して
```hello.d
import std.stdio;

void main() {
    writeln("Hello DLang!");
}
```
コンパイルします。
```zsh
dmd hello.d
# ldcの場合
# ldc2 hello.d
```
すると、C言語と同じように`hello`と`hello.o`というファイルが作成されます。
早速実行してみましょう。
```
./hello
```
「Hello DLang!」と出力されれば成功です。

# AtCoderで使ってみよう。
タイトル通り、AtCoderなど競プロの問題を解くときに必要になりそうな文法を中心に紹介していきます。

## UFCS(Uniform Function Call Syntax)
UFCSとは、関数の第1引数をレシーバーとして書ける文法上の機能です。D言語で採用されており、例えば`hoge(x, y)`を`x.hoge(y)`のように書けます。
メソッドチェインのように記述できてなかなか便利です。D以外で採用されている言語は少なく、業務で他の言語を書くときに「UFCSを使わせてくれ」と思ってしまいます。
業務のコードの場合、あまり繋げすぎると可読性が落ちたりデバッグしにくくなったりする点に気を使わないといけませんが、競プロだと書きやすさというメリットが際立ちます。

UFCSとは別に、Dの文法では引数0個の関数は`()`を省略できます。例えば、引数が1つだけの関数は以下のような書き方ができるというわけです。
```dlang
writeln("Hello");
// 以下のように書き換え可能
"Hello".writeln();
"Hello".writeln;
```

## 標準入出力
競プロとかコーディングテストとかをしたときに馬鹿にできないのが標準入力です。（私はAtCoderで標準入力に手間取って30分溶かしたことがあります。）標準入力の方法はしっかり予習して挑みましょう。
### case1: よくありがちな入力
2行目に空白区切りの配列、1行目にその配列の要素数が与えられるこんなやつ。
```
N
x_1 x_2 x_3 ... x_N
```

`readln`を使うのが簡単です。
```dlang
import std.stdio, std.string, std.conv;

void main() {
    // 1行目をintとして取得する
    int n = readln.chomp.to!(int);
    // 2行目をint[]として取得する
    int[] x = readln.chomp.split.to!(int[]);

    writeln(n, x); 
}
```
とりあえず、`readln.chomp.split`と詠唱します。
`readln()`で作られる文字列は行末の改行も含むため、`chomp()`で落とします。`split()`は引数を渡さない場合、空白で区切って`string`の配列を作ります。
### case2: `(a, b)`の組がいくつか渡されるやつ
```
N
a_1 b_1
a_2 b_2
...
a_N b_N
```

```dlang
import std.stdio, std.string, std.conv;

void main() {
    // 1行目
    int n = readln.chomp.to!(int);
    // 2行目以降
    int[] a = [], b = [];
    foreach(_; 0..n) {
        auto input = readln.chomp.split.to!(int[]);
        a ~= input[0];
        b ~= input[1];
    }
    
    writeln(a);
    writeln(b);
}
```
`foreach`で回して、動的配列に追加していきます。

`readf`を使うこともできます。C言語の`scanf`と若干挙動が違うようなので注意が必要です。
```dlang
    // foreachの中身を以下に変更
    int inputA, inputB;
    readf("%d %d\n", &inputA, &inputB);
    a ~= inputA;
    b ~= inputB;
```

### 出力
こちらは`writeln`や`writef`で迷わず書けます。使い方はCやJavaなどの`printf`と一緒です。
```dlang
import std.stdio;

void main() {
    int x = 42;
    writeln(x);
    writef("%d\n", x); // 42
}
```

### 配列の出力
解答で配列を
```
a_1 a_2 a_3 ... a_n
```

のように出力しなければならないときがあります。これは`join()`を使うと簡単に書けます。`join()`を使う際には配列を`string[]`にキャストしてやる必要があります。
最後の`.writeln`は、先ほど紹介したUFCSによって可能な記法です。

```dlang
import std.stdio, std.conv, std.array;

void main() {
    int[] answer = [2, 3, 5, 7, 11];
    
    answer.to!(string[])
        .join(" ")
        .writeln; // 2 3 5 7 11
}
```

## 高階関数
配列などに対して`map!`や`each!`、`filter!`といった高階関数を使えます。
使い方は概ね他の言語と一緒です。関数名の後ろの`!`を忘れないようにしましょう。

**ラムダが1行で書ける場合**
```dlang
import std.stdio, std.algorithm, std.array;

void main() {
    int[][] x = [[1, 1], [2, 3], [4, 5], [8, 7]];
    auto y = x.map!(a => a[0]).array;
    writeln(y); // [1, 2, 4, 8]    
}
```

**ラムダが複数行に渡る場合**
```dlang
import std.stdio, std.algorithm;

void main() {
    int[] x = [1, 1, 2, 3, 5, 8, 13];
    x.each!(
        (a) {
            if(a % 2 == 0) {
                writeln(a / 2);
            } else {
                writeln(a);
            }
        }
    ); // 1 1 1 3 5 4 13 が1行ごとに出力される
}
```
`map!`の後に`array()`を使うと配列に戻せます。
当然ですが、途中で配列の要素を追加/削除をするような処理は無理ですし、ループじゃないので途中で`break`は使えません。そのような処理が必要な場合は`foreach`や`while`でループを書きましょう。

話がそれますが、高階関数の文法に関してはKotlinの文法
```kotlin
hoge.map! { it -> it * 2 }
```
の方が直感的に書けて好きです。

### `iota()`と組み合わせて使う
`n.iota()`とすると`[0, 1, 2, .., n]`という`Range`が作成されます。これと高階関数を組み合わせて使うと、ループと似た感じで使えて便利だったりします。
```dlang
import std.stdio, std.range, std.algorithm;

void main() {
    int n = 5;
    int[] evenNumbers = n.iota.filter!(i => i % 2 == 0).array;
    writeln(evenNumbers); // [0, 2, 4]
}
```

## 配列の操作
### 値を指定して初期化する
`repeat()`を使います。
```dlang
import std.stdio, std.range;

void main() {
    int n = 5;
    int[] all1 = repeat(1, n).array;
    writeln(all1); // [1, 1, 1, 1, 1] 
}
```
ちなみに配列を以下のようにrepeatすると、同じ配列が参照されるので使い物になりません。
```dlang
import std.stdio, std.range;

void main() {
    int n = 5;
    int[][] all1 = repeat(1, n).array.repeat(n).array;

    all1[0][0] = 2; // 0行目の値を更新

    writeln(all1[1][0]); // 2が出力される。1 ~ 4行目も同じインスタンスを参照しているため。
}
```
競プロでまともにN×Nの配列を作る機会は(実行時間制限に引っかかりやすいため)稀な気がしますが、以下のような`iota`を使う方法が一例になるでしょうか。
```dlang
import std.stdio, std.range, std.algorithm;

void main() {
    int n = 5;
    int[][] all1 = n.iota.map!(i => repeat(1, n).array).array;

    all1[0][0] = 2; // 0行目の値を更新
    writeln(all1[1][0]); // 今度はちゃんと1が出力される
}
```

### ソートする
`sort()`を使います。`sort()`は副作用のある関数で、もとの配列を更新します。
```dlang
import std.stdio, std.algorithm;

void main() {
    int[] a = [1, 4, 1, 4, 2, 1, 3, 5, 6];
    a.sort;
    writeln(a); // [1, 1, 1, 2, 3, 4, 4, 5, 6]
}
```
`sort!()`を使うとソートの条件を指定することができます。
以下は自分で定義したクラスの特定のフィールドの値でソートをする例です。
```dlang
import std.stdio, std.algorithm, std.conv;

class User {
    string name;
    int age;

    this(string name, int age) {
        this.name = name;
        this.age = age;
    }

    override string toString() {
        return "(" ~ name ~ "," ~ age.to!string ~ ")";
    }
}

void main() {
    User user1 = new User("Taneshima", 17);
    User user2 = new User("Inami", 17);
    User user3 = new User("Todoroki", 20);
    User user4 = new User("Yamada", 16);
    User[] users = [user1, user2, user3, user4];

    // Userを年齢の降順でソートする
    users.sort!((a, b) => a.age > b.age);
    writeln(users); // [(Todoroki,20), (Inami,17), (Taneshima,17), (Yamada,16)]
}
```

ちなみにソート後に`unique()`を使うと、重複なしの配列ができあがります。
（配列からuniqueな要素を取り出すのは計算回数$O(n\log n)$でいけるんですね）

# FizzBuzzを実装してみよう

まだまだありますが、今回はここら辺にして実際に簡単なアルゴリズムを実装してみましょう。
以下の形の標準入力
```
N
```

から自然数Nを受け取って、1 ~ N までの整数のFizzBuzzを改行区切りで出力するということにしましょう。
ここまで紹介したもので大体書けるはずです。

```fizzBuzz.d
import std.stdio, std.string, std.range, std.algorithm, std.conv;

void main() {
    // 標準入力を取得
    int n = readln.chomp.to!int;

    // 解答を出力
    iota(1, n + 1).map!(
        (i) {
            if(i % 15 == 0) {
                return "FizzBuzz";
            } else if(i % 3 == 0) {
                return "Fizz";
            } else if(i % 5 == 0) {
                return "Buzz";
            } else {
                return i.to!string;
            }
        }
    ).array
    .join("\n")
    .writeln;
}
```
実行例（標準入力で15を与えた例）
```
❯ ./advent2024
15
1
2
Fizz
4
Buzz
Fizz
7
8
Fizz
Buzz
11
Fizz
13
14
FizzBuzz
```

業務のコードだと怒られそうですが、解答の出力をあえて1行で書いてみました。
時間制限のある競プロだと「そこそこの可読性を保って、ロジックを手早く書く」ことの方がありがたいので、Dとの相性の良さがわかると思います。

# まとめ

いかがでしたでしょうか。本日(アドベントカレンダー上の公開日)もAtCoderのコンテスト([ABC 383](https://atcoder.jp/contests/abc383))が予定されておりますので、ぜひD言語で参加してみてください。

業務では(当然ながら)Dを使わないので、Dを書くのを楽しみにAtCoderのコンテストに挑んでいる面もあります。プロ棋士の佐藤天彦九段の「居飛車は仕事、振り飛車は恋愛」に倣うと、「Java・Kotlinは仕事、Dは恋愛」とでも言ったところでしょうか。
とかいいつつ、業務で何かしらのデータをもとに大量のSQLを作成するときにD言語でスクリプトを作ってみたりしています。~~（恋愛の影響が仕事に出るタイプの人間）~~

- そもそもなぜDか
D言語くんをきっかけに以前からDに興味を持っていました。そのため、AtCoderを始めたときに使用言語としてDを選択したというのが経緯です。コーディングテストを受けるときは、学生時代によく使っていたCを選んでいたのですが、AtCoderで制限時間内にアルゴリズムを書くには不向きです。Cから他言語へ移行する際にちょうどDが適していました。個人的にはC++よりもDの方が移行しやすく感じました。

- AtCoderを始めてみて
決まった時間に集中してアルゴリズムを考えてコードを書くのがすごく楽しいです。まだ始めたばかりでレートは低いですがとりあえず茶色目指して頑張っていきたいと思います。
今のところは時間内にC問題までACを取る、D問題は時間内に着手して、翌週までにはACを取るくらいのつもりで解いています。　だんだんD言語にも慣れてきたので、そろそろ時間内でD問題までACを取れるようになりたいですね。
![スクリーンショット 2024-12-01 22.34.46.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3618312/81cd5bac-dd7d-8ffa-0806-0dfcb3270e5d.png)

以上、[TRIAL＆RetailAI Advent Calendar 2024](https://qiita.com/advent-calendar/2024/retail-ai) 7日目「D言語でAtCoderを解きたい！」でした。
明日は[@Carol_fan](https://qiita.com/Carol_fan)さんの「React Testing Library」という記事です。お楽しみに！

/*********
\* RetailAIとTRIALではエンジニアを募集しています。
\* 興味がある方はご連絡ください！
\* https://recruit.jobcan.jp/retail-ai/
*********/

# 参考
- [AtCoder](https://atcoder.jp/?lang=ja)
    - 基本的に毎週土曜の21:00 ~ 22:40にコンテストが開催されています。一緒にDで（Dじゃなくてもいいですが）参加しましょう！
- [DLang Tour(日本語版)](https://tour.dlang.org/tour/ja/welcome/welcome-to-d)
    - D言語くんが出迎えてくれます。
- [D言語くんの繁殖についての仮説](https://qiita.com/gobori/items/821e6d8219033c4f68a8)
    - D言語くんに関する、一番好きな考察(?)記事。
- [日本将棋連盟 棋士データベース(佐藤天彦九段)](https://www.shogi.or.jp/player/pro/263.html)
    - 福岡県福岡市出身であることを今知りました。