競プロD言語テンプレート2021
はじめに
競プロ用テンプレートをちょこちょこ育ててきて、個人的に良くなってきたなと感じたので2021年版として一旦、記事として残しておきます。
これがベストなテンプレートというわけではなく来年には全く違ったものを利用しているかもしれません。
競プロテンプレート
void solve() {
}
void main() {
// 入力
// 前処理
init();
// 解答
solve();
}
void init() {
}
import std;
const long MOD = 10^^9+7;
alias PQueue(T, alias less="a<b") = BinaryHeap!(Array!T, less);
string instr() { return readln.chomp; }
T inone(T=int)(){return readln.chomp.to!T;}
void inelm(L...)(ref L A){ auto l = readln.split;
foreach(i, T; L) A[i]=l[i].to!T; }
void appendElm(L...)(ref L A){ auto l = readln.split;
foreach(i, T; L) A[i]~=l[i].to!(typeof(A[i].front));
}
T[] inarr(T = int)(){ return readln.split.to!(T[]); }
T convn(T=int)(char c){ return (c-'0').to!T; }
bool chmin(T=long)(ref T a, const T b) { if(a>b) {a=b; return true;} return false; }
bool chmax(T=long)(ref T a, const T b) { if(a<b) {a=b; return true;} return false; }
class UnionFind {
int[] par, rank;
this(int n) { par.length = rank.length = n; foreach(i; 0..n) par[i] = i; }
int find(int x) { if (par[x] == x) return x; else return par[x] = find(par[x]); }
void unite(int x, int y)
{
x = find(x); y = find(y);
if(x==y) return;
if(rank[x] < rank[y]) par[x] = y;
else { par[y] = x; if (rank[x] == rank[y]) rank[x]++; }
}
bool same(int x, int y) { return find(x) == find(y); }
}
double degToRad(double degree) {
return degree * PI / 180.0;
}
double radToDeg(double radian) {
return radian * 180.0 / PI;
}
T getSumDigit(T=long)(T N) {
T ret;
foreach(e; N.to!string) {
ret += e - '0';
}
return ret;
}
処理の流れ
入力
問題で入力として与えられる変数はグローバル変数としています。
main() の // 入力 以下で入力を受け取ります。
前処理
初期化処理が必要な場合は、簡単なものでも init() 内に記述します(D言語は整数型はデフォルトで0で初期化されるので不要な場合も多いですが)。
例えば、座圧とか、累積和とかの前処理などで使うイメージです。
解答
solve()に実際の解答を記述します。
解答の処理をしながら出力する場合はこのまま利用します。
しかし、値をひとつだけ出力する場合にはsolve()の戻り値を void から long とかに書き換えて次のようにしています。
long solve() {
return 0;
}
void main() {
...
// 解答
solve().writeln();
}
Yes, No 問題であれば次のようにしています。
bool solve() {
return true;
}
void main() {
...
// 解答
writeln( solve() ? "Yes" : "No" );
}
入力で利用する関数
入力で利用する関数は問題にかかわらずよく利用するので紹介しておきます。
その他の関数やクラスは特定の形式の問題でのみ利用するため特に紹介しません。
競プロの入力の形式でよく見るものはパターン化して簡単に入力を受け取れるようにしています。
次の関数を利用すれば大抵のパターンはこなせる気がします。
inone()
入力が次のようなもので与えられる、変数が1つの入力で利用しています。
N
次のような形で利用します。
int a = inone(); // N が int
long b = inone!long(); // N が long
double c = inone!double(); // N が double
instr()
入力が次のようなもので与えられる、変数が1つの入力でかつそれが文字列の場合に利用します。
S
次のような形で利用します。
string s = instr();
やっているとはstring s = inone!string();であるので実はinone()で事足ります。
しかし、文字列のみの入力って出ることが多いので特別に定義しています。
inelm()
入力が次のようなもので与えられる、変数が一行で複数の場合に利用します。
N K S
次のような形で利用します。
long N;
int K;
string S;
inelm(N, K, S);
型を考えずに、最初に定義した変数で受け取れるので便利です。
appendElm()
入力が次のようなもので与えられる、変数が複数行に渡って与えられる場合に利用します。
a_1 b_1 c_1
...
a_n b_n c_n
次のような形で利用します。
int N; // 何行の入力があるか
int[] a, b, c;
foreach(i; 0..N) {
appendElm(a, b, c);
}
最近追加しました。利用する際にforループを回さない実装も少し考えましたが、
入力に関する関数は全て1行ずつに対応しているので合わせました。
実際、そのほうが見やすい気がしています。
inarr()
入力が次のようなもので与えられる、変数が一行に複数与えられる場合に利用します。
a_1 a_2 ... a_n
次のような形で利用します。
int[] a = inarr(); // int で受け取る場合
long[] b = inarr!long(); // long で受け取る場合
double[] c = inarr!double(); // double で受け取る場合
改善点
私が問題を解く中で必要なものを足していっている状態なのでまだまだ足りないものが多くあります。
より沢山の問題を解いて必要な関数やクラスを増やしていきたい。
また、強い競プロerは関数の高速化等を行っていますが、現在は処理速度等はあまり考慮していません (今のレーティング帯だと、解ける問題を増やすことの方が重要なため）。
高速化も考えていけるようにはなりたい。
最後に
D言語の競プロテンプレートはC++, Python に比べれば需要がない気がします！
でも、D言語で競プロは最高なので今の自分のテンプレートを紹介しておきました！
よろしくおねがいします。
Discussion