AtCoder に登録したら解くべき精選過去問 10 問を D言語ワンライナー で解いてみた
最近やっている人が多いので便乗
元ネタはこれ↓
ここで紹介されている問題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
は要らないです
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
は、第一引数にテンプレートのラムダ式を適用させたものを返す関数です。これがあれば大概の問題は脳死でワンライナーで解けます。(ただし見た目かっこ良くないしロマンがないので多用は避けたい)
ABC081A Placing Marbles
import std.stdio : readln, writeln; import std.string : chomp; import std.algorithm : count; void main() { readln.chomp.count('1').writeln; }
count
は、「値を引数に取るバージョン」や「ラムダ式をテンプレート引数に取るバージョン」や「ただ要素数を数えるだけのバージョン」などがあるので使い分けられると便利です。
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
は知っておくとたのしいです。
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
を知りました。
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; }
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; }
を計算して出力してます
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
で重複を除去してます。
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からカンマ演算子の演算結果の使用がエラーになってしまったので、今回はカンマ演算子の使用は控えました。
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
によってそのうち空配列になります。
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
が使えたら最初の部分はもう少しスッキリと書けます。
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); } } } }
のように定義してます。