D言語で解く AtCoder Beginner Contest 161 (A〜D)

AtCoder Beginner Contest 161に参加したのでその記録です

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

tempalte.d

import std.stdio,std.math,std.string,std.conv,std.typecons,std.format;
import std.algorithm,std.range,std.array;

T[] readarr(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;}

//END OF TEMPLATE

A - ABC Swap

問題文

言うに及ばず

a.d

void main(){
    long x,y,z;
    scan(x,y,z);
    writefln("%s %s %s",z,x,y);
}

B - Popular Vote

問題文

b.d

void main(){
    ulong m,n;
    ulong[] a;
    scan(n,m);
    a=readarr!ulong;
    auto sum=a.csum;
    (a.filter!(x=>x.to!real>=sum.to!real/(4*m).to!real
        ).array.length>=m?"Yes":"No").writeln;
}

auto csum(ulong[] a){
    ulong tmp;
    foreach(t;a)tmp+=t;
    return tmp;
}

本当はauto sum=a.fold!"a+b"とできればどれだけ簡単なことか
AtCoderのバージョンではfoldが使えないのです。クソが

と思っていたらstd.algorithm.sumとかいう合計を求めてくれる関数があった。知らなかった...

C - Replacing Integer

問題文
n+1回目の操作によってできるxの数列を$ \{ x_n \} $とすると、$x_1=N,\ x_{n+1}=|x_n-K|$
であるから、最小の$x_n$はN % Kかabs(N % K - K)のどちらかです。

c.d

void main(){
    long n,k;
    scan(n,k);
    min(n%k,abs(n%k-k)).writeln;
}

D - Lunlun Number

問題文
幅優先探索を使いました。D言語のQueueってstd.container読んでもイマイチよくわからないんですよねDList使ってあとは勝手に書けってこと？

d.d

void main(){
    ulong k;
    k.scan;
    k.solve.writeln;
}
 
struct Queue{
    public:
    char[][] list;
    auto enq(char c){list~=[c];}
    auto enq(char[] c){list~=c;}
    auto deq(){auto d=list[0];list=list.length==1?[]:list[1..$];return d;}
}
 
char[] co(char c){
    if(c=='0')
        return ['0','1'];
    if('1'<=c&&c<='8')
        return [to!char(c-1),c,to!char(c+1)];
    if(c=='9')
        return ['8','9'];
    assert(0);
}
 
auto solve(ulong k){
    Queue q;
    foreach(c;'1'.to!char..('9'+1).to!char)q.enq(c);
    foreach(i;0..k-1){
        auto tmp=q.deq;
        foreach(s;tmp[$-1].co)
            q.enq(tmp~s);
    }
    return q.deq;
}

まずキューに1から9までの数を順にエンキューします(1桁の整数は全てルンルン数です)。
その後、2桁のルンルン数を作っていきます。leading zeroなしなので、十の位は1から9までです。
char[] co(char)は、0から9までの「数字」に対して、差が1以下の「数字」を小さい順に返す関数です。キューの中身(1〜9)を順番に

• デキューして取っておく(tmp=q.deq)
• tmpの末尾にco(tmp)の返り値をそれぞれくっつけ、順にエンキューする

ということを繰り返すと、キューの中身は10,11,12,21,22,23,32,33,34,...,98,99となります。
以降も同じように続けるとルンルン数が小さい順に生成されていきます。
この作業をK-1回続け、最後にもう一回デキューした内容がK番目のルンルン数です。

E - Yutori

次回か次次回くらいには解けるようにしたいです

感想

始まる15分前くらいまで寝てたので、頭が働かずC問題までに時間がかかった
sumのこととかもあり、ちゃんとPhobosを読み直そうと思った。
競プロ界の鉄板本とも呼ばれる蟻本を買ったのですが、かなりイイです（あれがないとD問題とか思いつかない）
まだ最初の方しか読んでないので、来週の162までにもう少し読み進めておくつもりです