AtCoder に登録したら解くべき精選過去問 10 問を D言語ワンライナーで解いてみた

最近やっている人が多いので便乗

元ネタはこれ↓

qiita.com

ここで紹介されている問題10問を各プログラミング言語で解くみたいなのが流行ってるみたいです。

D言語とワンライナーが好きなのでD言語ワンライナーで解いていきます。

問題一覧はここ。

よく見たら一問目の入出力チュートリアルも含めて11問ありますね

既にあるD言語ver

AtCoderに登録したら解くべき精選過去問10問をD言語で解いてみた（竹雄さん）
AtCoderに登録したら解くべき精選過去問10問をD言語で解いてみた - D言語の構文と標準ライブラリを使い倒す編（Yousackさん）
AtCoderに登録したら解くべき精選過去問10問をD言語で解いてみた（よすぽさん）

もう二番煎じ感半端ないですが、D言語好きとしては乗るしかないでしょう。このビッグウェーブに

コードの方針

ワンライナーの制約をつけます

main関数内は文が一つのみ。
標準ライブラリは自由にimportして使って良い。
main関数の外には関数やクラスなどを定義しない。

便利な標準ライブラリ関数群とUFCSを連携させると楽しくコーディングできる(?)ことが伝わるといいな

各関数がどっから引っ張ってきたのかすぐわかるようにimport文のところにすべて記述しました。

PracticeA はじめてのあっとこーだー（Welcome to AtCoder）

import std.stdio : readln, writeln;
import std.conv : to;
import std.range : join, split, repeat;
import std.algorithm : map, sum;
import std.string : chomp;
import std.container : make, Array;

void main() {
    (
        () => readln.split.to!(long[])
    ).repeat(2).map!"a()".join.sum.to!string.make!Array(readln.chomp)[].join(" ").writeln;
}

splitの直前にchompは要らないです

→ Submission #2249263

ABC086A Product

import std.stdio : readln, writeln;
import std.conv : to;
import std.range : split;
import std.algorithm : reduce;
import std.functional : pipe;

void main() {
    ["Even", "Odd"][readln.split.to!(long[]).reduce!"a*b".pipe!"a%2"].writeln;
}

pipeは、第一引数にテンプレートのラムダ式を適用させたものを返す関数です。これがあれば大概の問題は脳死でワンライナーで解けます。（ただし見た目かっこ良くないしロマンがないので多用は避けたい）

→ Submission #2249251

ABC081A Placing Marbles

import std.stdio : readln, writeln;
import std.string : chomp;
import std.algorithm : count;

void main() {
    readln.chomp.count('1').writeln;
}

countは、「値を引数に取るバージョン」や「ラムダ式をテンプレート引数に取るバージョン」や「ただ要素数を数えるだけのバージョン」などがあるので使い分けられると便利です。

→ Submission #2249261

ABC081B Shift only

import std.stdio : readln, writeln;
import std.conv : to;
import std.range : repeat, back, generate, split, array;
import std.algorithm : map, countUntil, reduce, min;

void main() {
    (() => readln).repeat(2).map!"a()".array.back.split.to!(long[]).map!"a*2".map!(
        a => generate!(
            () => a /= 2
        ).countUntil!"a%2!=0"
    ).reduce!min.writeln;
}

generateは知っておくとたのしいです。

→ Submission #2249360

ABC087B Coins

import std.stdio : readln, writeln;
import std.conv : to;
import std.string : chomp;
import std.range : iota;
import std.algorithm : map, count, cartesianProduct;
import std.functional : pipe;

void main() {
    (() => 0.iota(readln.chomp.to!long + 1)).pipe!(
        f => cartesianProduct(f(), f(), f())
    ).map!(
        as => 500*as[0] + 100*as[1] + 50*as[2]
    ).count(readln.chomp.to!long).writeln;
}

よすぽさんの記事を見てcartesianProductを知りました。

→ Submission #2249674

ABC083B Some Sums

import std.stdio : readln, writeln;
import std.conv : to;
import std.range : split, iota;
import std.algorithm : filter, map, sum;
import std.functional : pipe;

void main() {
    (
        as => iota(1, as[0]+1).filter!(
            x => x.to!string.map!(c => c.to!string.to!long).sum.pipe!(
                y => as[1]<=y && y<=as[2]
            )
        ).sum
    )(readln.split.to!(long[])).writeln;
}

→ Submission #2249987

ABC088B Card Game for Two

import std.stdio : readln, writeln;
import std.conv : to;
import std.range : array, back, enumerate, split, repeat;
import std.algorithm : map, sort, sum;

void main() {
    (
        () => readln
    ).repeat(2).map!"a()".array.back.split.to!(long[]).sort!"a>b".enumerate.map!(
        a => a.value * (a.index%2==0 ? 1 : -1)
    ).sum.writeln;
}

$\displaystyle\sum_{i=1}^N (-1)^{i-1} a_i$ を計算して出力してます

→ Submission #2249822

ABC085B Kagami Mochi

import std.stdio : readln, writeln;
import std.conv : to;
import std.string : chomp;
import std.range : array, split, repeat;
import std.algorithm : map, sort, uniq, count;

void main() {
    (
        () => readln.split.to!(long[])
    ).repeat(readln.chomp.to!long).map!"a()".array.sort!"a>b".uniq.count.writeln;
}

sort!"a>b".uniqで重複を除去してます。

→ Submission #2249839

ABC085C Otoshidama

import std.stdio : readln, writeln;
import std.conv : to;
import std.range : split, iota, join, only, tee, array, front;
import std.algorithm : map, reduce;

void main() {
    (
        as => false.reduce!(
            (exists, bs) => exists || (
                10000*bs[0] + 5000*bs[1] + 1000*bs[2] == as[1] && (
                    true.only.tee!(
                        _ => bs.map!(to!string).join(" ").writeln
                    ).array.front
                )
            )
        )(
            0.iota(as[0]+1).map!(
                i => 0.iota(as[0]-i+1).map!(
                    j => [i, j, as[0]-i-j]
                )
            ).join
        ) || writeln("-1 -1 -1")
    )(readln.split.to!(long[]));
}

これが一番面倒でした。||と&&の短絡評価を悪用利用して実現しました。

true.only.tee!(
    _ => bs.map!(to!string).join(" ").writeln
).array.front

のところは(bs.map!(to!string).join(" ").writeln, true)と実質等価です。最新版のdmd2.079.0からカンマ演算子の演算結果の使用がエラーになってしまったので、今回はカンマ演算子の使用は控えました。

→ Submission #2250266

ABC049C 白昼夢 / Daydream

import std.stdio : readln, writeln;
import std.conv : to;
import std.string : chomp;
import std.range : retro, generate, back, array, take;
import std.algorithm : reduce, min, startsWith;
import std.array : empty;
import std.functional : pipe;

void main() {
    readln.chomp.retro.to!string.pipe!(
        s => generate!(
            () => s = s.reduce!(
                (a, b) => a.startsWith(b) ? a[min($, b.length)..$] : a
            )(["maerd", "remaerd", "esare", "resare"])
        ).take(20000).array.back.empty ? "YES" : "NO"
    ).writeln;
}

20000は適当な十分に大きい数です。条件を満たす入力ならgenerateによってそのうち空配列になります。

→ Submission #2251639

ABC086C Traveling

import std.stdio : readln, writeln;
import std.conv : to;
import std.string : chomp;
import std.range : front, back, repeat, split, zip, array;
import std.algorithm : map, all;
import std.math : abs;
import std.functional : pipe;

void main() {
    (
        [0L, 0L, 0L] ~ (
            () => readln.split.to!(long[])
        ).repeat(readln.chomp.to!long).map!"a()".array
    ).pipe!(
        as => zip(as[0..$-1], as[1..$])
    ).map!(
        a => zip(a[0], a[1]).map!(
            b => abs(b[1]-b[0])
        )
    ).all!(
        as => as[0] >= as[1]+as[2] && as[0]%2 == (as[1]+as[2])%2
    ).pipe!(
        a => a ? "Yes" : "No"
    ).writeln;
}

zipとmapでごにょごにょ配列をいじるとできます。

dmd2.079.0で追加されたstd.range.slideが使えたら最初の部分はもう少しスッキリと書けます。

→ Submission #2251538

Dの標準ライブラリに関する諸々

競プロで有効な便利標準ライブラリ関数はstd.rangeとstd.algorithmにたくさんあります。暇なときにでもdocumentationを眺めてみてはどうでしょうか？

データ構造に関してはstd.containerに双方向連結リストや赤黒木などがあります。不足気味ではありますがDlistがstackやqueueの役割も担ってくれたりとそこまで深刻ではないです。ただ、使い方にくせがあるので慣れておく必要はあるかも知れません。

あと、ジャッジサーバーのコンパイラが古くて「○○の標準関数がない」みたいなときはstatic if(コンパイラバージョンの比較)で定義するという手があります。

例えばstd.algorithm.foldはreduceと引数の順序が異なる関数なのですが、これはdmd2.071.0で追加された関数です。

僕は競プロ用のテンプレートとして

// fold was added in D 2.071.0
static if (__VERSION__ < 2071) {
    template fold(fun...) if (fun.length >= 1) {
        auto fold(R, S...)(R r, S seed) {
            static if (S.length < 2) {
                return reduce!fun(seed, r);
            } else {
                return reduce!fun(tuple(seed), r);
            }
        }
    }
}

のように定義してます。

Ark's Blog

引っ越しました→ https://blog.arkark.dev/