D言語で競プロをする際に注意すること

はじめに

D言語で競プロをしていて、標準ライブラリ Phobos を使用する中で個人的にハマったポイントを紹介します。

powmod は自作しよう

$x ^ n \pmod{m}$を計算するとき、繰り返し二乗法を使用すると $O(\log{n})$ で求めることができます。¹

long powMod(long x, long n, long m) {
    long ret = 1;
    while (n > 0) {
        if (n % 2 == 1) {
            ret *= x;
            if (ret > m) ret %= m;
        }
        x *= x;
        if (x > m) x %= m;
        n /= 2;
    }
    return ret;
}

標準ライブラリには powmod が用意されていますが、引数の型によって処理速度が変わるので注意が必要です。

powmod の引数には符号なし整数型である ushort、 uint および ulong を使用できますが、$x$ と $m$ のどちらかの型が ulong の場合は処理速度が低下します。ulong 型を使用するとオーバーフローを防ぐために繰り返し二乗法の要領で乗算するので $O(\log{n}\log{m})$かかります。²

ulong を使用した場合

uint を使用した場合

制約で $m$ の値が32bitに収まる場合は uint にキャストするか自作の関数を使用しましょう。

import std; は慎重に

import std; と書くと標準ライブラリのすべてのモジュールをインポートできますが、関数のコンフリクトの恐れがあるので注意が必要です。

例えば string 型に stride 関数を使用するとコンフリクトします。実際に自分は弊社が10月に主催した ABC323 のA問題を解く際にハマってしまいました。

問題は、与えられた文字列が0と1から構成されており、偶数番目の文字がすべて0であるかを判定するものです。
これに対してstride関数 を使って以下のようコードを書きました。

import std;

void main() {
    string S;
    readf("%s\n", S);

    string res = stride(S[1..$], 2).all!"a == '0'" ? "Yes" : "No";
    res.writeln;
}

しかし、実行すると以下のエラーが発生します。

abc323a.d(7): Error: `stride` matches conflicting symbols:
/dlang/dmd-2.104.0/linux/bin64/../../src/phobos/std/utf.d(383):        function `std.utf.stride!string.stride`
/dlang/dmd-2.104.0/linux/bin64/../../src/phobos/std/range/package.d(513):        function `std.range.stride!string.stride`
abc323a.d(7): Error: none of the overloads of template `std.algorithm.searching.all!"a == '0'".all` are callable using argument types `!()(uint)`
/dlang/dmd-2.104.0/linux/bin64/../../src/phobos/std/algorithm/searching.d(121):        Candidate is: `all(Range)(Range range)`
  with `Range = uint`
  whose parameters have the following constraints:
  `~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~`
`  > isInputRange!Range
      - __traits(isTemplate, pred)
        or:
      - is(typeof(unaryFun!pred(range.front)))
`  `~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~`
  Tip: not satisfied constraints are marked with `>`
Failed: ["/dlang/dmd-2.104.0/linux/bin64/dmd", "-v", "-o-", "abc323a.d", "-I."]

std.range.stride と std.utf.stride がコンフリクトしていると言われます。

回避するには import std; を使わず必要なモジュールだけインポートするか、どの関数を使用するか指定しましょう。

string res = std.range.stride(S[1..$], 2).all!"a == '0'" ? "Yes" : "No";

おわりに

D言語で競プロしましょう。

1. 「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜 ↩

2. Fix Issue 6244 - Add powmod / modpow function to std.math #5761 ↩