D言語で解く Judge System Update Test Contest 202004

今回AtCoderの実行環境が更新され、多くの言語でバージョンアップが入りました。
これに付随して実施された[Judge System Update Test Contest 202004](https://atcoder.jp/contests/judge-update-202004)に参加したので、その記録です。

#D言語に関するアップデート
|環境|変更前|変更後|
|:--|:----|:-----|
|dmd|v2.071.1|v2.091.0|
|gdc|v4.9.4|v9.2.1|
|ldc|v0.17.0|v1.20.1|

環境更新前最後のコンテストとなった[ABC 161](https://atcoder.jp/contests/abc161)でのD言語による提出数を比較するとdmdが127件、gdcが0件、ldcは15件(2020/4/7/16:30)となっていることからも判る通り、多くの参加者はdmdを使っています。

UFCSが効かなくて同名のdeprecatedなpropertyが呼ばれたり、foldが使えなくて怒られたり、そういったイライラCEが無くなりそうでとても嬉しいです。

#テンプレート
各提出の冒頭でこんな感じのテンプレート使ってます

```d
import std;

T[]reedarr(T=long)(){return readln.chomp.split.to!(T[]);}
void scan(T...)(ref T args){auto input=readln.chomp.split;foreach(i,t;T)args[i]=input[i].to!t;}
struct Queue(T){T[]e;auto enq(T t){e~=t;}auto enq(T[]ts){e~=ts;}T deq(){T tp=e[0];e=e.length>1?e[1..$]:[];return tp;}}
struct Stack(T){T[]e;auto push(T t){e~=t;}auto push(T[]ts){e~=ts;}T pop(){T tp=e[$-1];e=e.length>1?e[0..$-1]:[];return tp;}}
//END OF TEMPLATE
```

`import std;`で全部importできるのが良いですね。テンプレがスッキリしたようなしてないような感じです。

#A - Walking Takahashi
[問題文](https://atcoder.jp/contests/judge-update-202004/tasks/judge_update_202004_a)
chokudaiさん問題らしいです

```d:a.d
void main(){
    long s, l, r;
    scan(s, l, r);
    (s<l?l:r<s?r:s).writeln;
}
```

C++だと`std::clamp`というのがあるらしいですね。知らんけど。

#B - Picking Balls
[問題文](https://atcoder.jp/contests/judge-update-202004/tasks/judge_update_202004_b)

```d:b.d
void main(){
    long n;
    scan(n);
    auto x = new long[n];
    auto c = new char[n];
    iota(n).each!(i => scan(x[i], c[i]));
    long[] r, b;
    iota(n).each!((i){
        if(c[i] == 'R') r ~= x[i];
        else b ~= x[i];
    });
    r.sort.each!writeln;
    b.sort.each!writeln;
}
```

多分最適ではないとは思いますが、高々$n=100$なのでド直球です。

#C - Numbering Blocks
[問題文](https://atcoder.jp/contests/judge-update-202004/tasks/judge_update_202004_c)

最初は動的計画法かと思いちょっと面倒なことをしてたのですが、Twitterを見ていると深さ優先探索が一番シンプルに書けそうでした。

```d:c.d
long[] a;
 
void main(){
    a = reedarr;
    dfs(0,0,0,a.sum).writeln;
}
 
auto dfs(long x, long y, long z, long n){
    if(x>a[0] || y>a[1] || z>a[2])
        return 0;
    else if(x<y || y<z)
        return 0;
    else if(n==0)
        return 1;
    else
        return dfs(x+1,y,z,n-1) + dfs(x,y+1,z,n-1) + dfs(x,y,z+1,n-1);
}
```

整数の書き込み方を「どのような順番で置くか」という問題に置き換えられると、すぐにDFSに行き着きそうです。僕はダメでした。

#D - Calculating GCD
[問題文](https://atcoder.jp/contests/judge-update-202004/tasks/judge_update_202004_d)

こちらも累積gcdに気づかず、他の方のツイートを見て理解しました

```d:d.d

void main(){
    long n,q;
    scan(n,q);
    auto a=readarr;
    iota(n-1).each!(i => a[i+1] = gcd(a[i],a[i+1]));

    foreach(x;readarr){
        long l=-1, r=n;
        while(r-l>1){
            auto i = (l+r)/2;
            if(gcd(a[i],x) == 1)
                r = i;
            else
                l = i;
        }
        (r<n?r+1:gcd(a[$-1],x)).writeln;
    }   
}
```

${\rm gcd}(a_1,a_2,...,a_n)={\rm gcd}(...{\rm gcd}({\rm gcd}(a_1,a_2),a_3)...,a_n)$という結合法則を使い、`a[i]`を`a[0..i+1]`の累積gcdにします。
あとは二分探索で`gcd(a[i],x)==1`になるような最小のiを探しています。
ただ$O(\log n)$のために面倒くさい二分探索を書くより$O(n)$でいいから左から走査したくなるのですが、$n=10^5$というのはどんなもんなんでしょうか...

#感想
いつもの手元環境と実際の挙動が同じというのは精神衛生上ありがたい話です。
今回はそこまでバージョンアップの恩恵を受けられるような問題はありませんでしたが、次回以降のコンテストに期待です。