Help us understand the problem. What is going on with this article?

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

今回AtCoderの実行環境が更新され、多くの言語でバージョンアップが入りました。
これに付随して実施されたJudge System Update Test Contest 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でのD言語による提出数を比較するとdmdが127件、gdcが0件、ldcは15件(2020/4/7/16:30)となっていることからも判る通り、多くの参加者はdmdを使っています。

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

テンプレート

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

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

問題文
chokudaiさん問題らしいです

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

問題文

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

問題文

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

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

問題文

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

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$というのはどんなもんなんでしょうか...

感想

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

JJ1LIS
どこにでもいる普通の高校生 AtCoderはじめました D言語の力でC++を駆逐したいです
https://github.com/jj1lis
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away