D言語について語りたい

~アルゴリズム・データ構造編~

kokatsu

自己紹介

kokatsu

  • D言語で競プロしています(AtCoder水色)
  • ハックバーには月1、2回通っています

最初に

このLTではD言語について熱く語ります

比較のために競プロでよく使われているC++とPythonと比較します

C++やPythonを批判する意図はございません

今回紹介するアルゴリズム・データ構造はけんちょんさん著の鹿本から引用しています

詳しく知りたい方はぜひお買い求め下さい

D言語って何？

D言語は

基本文法がC/C++に似ていながら

Pythonのような書きやすさがある

D言語の(個人的に)
便利なところ

二重forループでこのようなミスをしたことありませんか?

for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; i++) {
        //
    }
}

競プロではC++でこのようなマクロが用いられます

#define rep(i, n) for (int i = 0; i < (int)(n); i++)

rep(i, N) {
    rep(j, N) {
        //
    }
}

D言語ではforeachを使うことで同じようなことができます

foreach (i; 0 .. N) {
    foreach (j; 0 .. N) {
        //
    }
}

foreachは配列に対しても使うことができます

int[] a = [3, 1, 4, 1, 5, 9, 2];
foreach (x; a) {
    x.writeln;
    // writeln(x);
}

配列の要素とともにインデックスを取得することもできます

int[] a = [3, 1, 4, 1, 5, 9, 2];
foreach (i, x; a) {
    writeln(i, " ", x);
}

foreach_reverseを使うことで逆順もできます

foreach_reverse (i; 0 .. N) {
    //
}

int[] a = [3, 1, 4, 1, 5, 9, 2];
foreach_reverse (i, x; a) {
    writeln(i, " ", x);
}

それではアルゴリズム・データ構造にはいっていきます

連長圧縮

"AAABBBBBAACDD"といった文字列を

(‘A’, 3), (‘B’, 5), (‘A’, 2), (‘C’, 1), (‘D’, 2)

のように圧縮すること

C++の場合(鹿本より)

// 長さ N の文字列 S が与えられたとする
for (int i = 0; i < N;) {
    // 初めて S[j] != S[i] となる場所を求める
    int j = i;
    while (j < N && S[j] == S[i]) {
        ++j;
    }

    // 文字 S[i] が j - i 文字連続したことがわかる
    cout << S[i] << j - i << endl;

    // i を j のところへワープさせる
    i = j;
}

Pythonの場合(鹿本より)

# 長さ N の文字列 S が与えられたとする
i = 0
while i < N:
    # 初めて S[j] != S[i] となる場所を求める
    j = i
    while j < N and S[j] == S[i]:
        j += 1

    # 文字 S[i] が j - i 文字連続したことがわかる
    print(S[i], j - i)

    # i を j のところへワープさせる
    i = j

D言語の場合は?

標準ライブラリに連長圧縮を求めるgroup関数があります

auto G = S.group.array;
foreach (g; G) {
    writeln(g[0], g[1]);
}

D言語には競プロで使いそうな関数が標準ライブラリにあります

  • powmod($a ^ x$を$M$で割った余りを求める)
  • fft(高速フーリエ変換)
  • levenshteinDistance(二つの文字列がどの程度異なっているかを示す距離 問題例:けんちょんさんが作問したyukicoder No.225)

累積和

長さ $N$ の配列 $A$ に対して

$S[0] = 0$

$S[1] = S[0] + A[0]$

$S[2] = S[1] + A[1]$

…

$S[N] = S[N-1] + A[N-1]$

となる長さが $N + 1$ の配列 $S$ のこと

つまり$1 \leq i \leq N$において

$S[i] = A[0] + A[1] + … + A[i-1]$

となる

累積和を用意しておくことで

$0 \leq L \leq R \leq N - 1$を満たす$L$、$R$において

$A[L] + A[L+1] + … + A[R]$

を$S[R+1] - S[L]$を計算することで

高速で求めることができる

C++の場合(鹿本より)

vector<int> S(N+1, 0);
for (int i = 0; i < N; ++i) {
    S[i+1] = S[i] + A[i];
}

Pythonの場合(鹿本より)

S = [0] * (N + 1)
for i in range(N):
    S[i+1] = S[i] + A[i]

C++やPythonには

標準ライブラリに累積和を求める関数がある

C++の場合:exclusive_scan

A.emplace_back(0);
vector<int> S(N+1, 0);
exclusive_scan(A.begin(), A.end(), S.begin(), 0);

Pythonの場合:accumulate

S = [0] + list(itertools.accumulate(A))

D言語にも累積和を求めることができる関数がある cumulativeFold

int[] S = [0] ~ A.cumulativeFold!"a + b".array;

これらの関数を用いることで

他の累積〇〇を求めることができる

累積max

$S[0] = A[0]$

$S[1] = max(S[0], A[1])$

…

$S[N-1] = max(S[N-2], A[N-1])$

つまり$0 \leq i < N$において

$S[i] = max(A[0], A[1], …, A[i])$

となる

C++の場合

vector<int> S(N);
exclusive_scan(A.begin(), A.end(), S.begin(), A[0],
                [](int a, int b) { return max(a, b); });

Pythonの場合

S = list(itertools.accumulate(A, max))

D言語の場合

int[] S = A.cumulativeFold!max.array;

cumulativeFold関数

int[] S = [0] ~ A.cumulativeFold!"a + b".array;

int[] S = A.cumulativeFold!max.array;

!の後の"a + b"やmaxはテンプレートパラメータ

D言語はテンプレートパラメータが便利

配列をソートするとき

C++の場合

vector<int> A = {3, 1, 4, 1, 5, 9, 2};
sort(A.begin(), A.end()); // 昇順 [1, 1, 2, 3, 4, 5, 9]
sort(A.begin(), A.end(), greater<>()); // 降順 [9, 5, 4, 3, 2, 1, 1]

Pythonの場合

A = [3, 1, 4, 1, 5, 9, 2]
A.sort() # 昇順 [1, 1, 2, 3, 4, 5, 9]
A.sort(reverse=True) # 降順 [9, 5, 4, 3, 2, 1, 1]

D言語の場合

int[] A = [3, 1, 4, 1, 5, 9, 2];
A.sort; // 昇順 [1, 1, 2, 3, 4, 5, 9]
A.sort!"a > b"; // 降順 [9, 5, 4, 3, 2, 1, 1]

グラフの最短距離を求めるダイクストラ法を

優先度付きキューBinaryHeapを使って実装する場合

struct Edge {
    int to; // 隣接頂点番号
    long weight; // 重み
}

// 注意!! sortとは比較方向が異なる
// これはEdgeのweightが小さい順に慣れべている
auto heap = new BinaryHeap!(Array!Edge, "a.weight > b.weight")();

構造体の要素を用いて優先度付けすることができる

D言語の良さをわかっていただけましたでしょうか？

ご清聴ありがとうございました

参考文献

  • 大槻兼資. アルゴリズム的思考力が身につく! プログラミングコンテストAtCoder入門. KADOKAWA, 2022
  • 大槻兼資. 問題解決力を鍛える!アルゴリズムとデータ構造. 講談社, 2020