競技プログラミングは制限時間内に効率よくコーディングする必要があるので、必要なヘッダーや定義を予め書き込んだテンプレートを作っておきましょう。解答を作るときにまずテンプレートファイルをコピペして、そこから始めるようにします。決まった内容は無いので自分なりに工夫して便利なものを作ってください。他人の解答例を見ているときに参考になるものを見つけたら自分のテンプレートに追加して蓄積します。以下にC++のテンプレートのサンプルを示します。
ヘッダーファイル
筆者は HEADER.cpp というファイル名で、ヘッダーファイルのテンプレートを作ってあります。これは一例であり、日々更新を加えて改善しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include <bits/stdc++.h> using namespace std; using ll = long long; const int INF = 0x7FFFFFFF; const long long LINF = 0x7FFFFFFFFFFFFFFF; #define rep(i, n) for (int i = 0; i < (int)(n); i++) //--------------------------------------------------- // 問題 // 解説 int main() { int N; cin >> N; int S[N]; rep(i, N) cin >> S[i]; return 0; } |
この内容を以下に説明します。
インクルード文
コンパイラにGCC（コマンド名はg++）を使う前提で、まず次の２行を記述します。
|
1 2 |
#include <bits/stdc++.h> using namespace std; |
1行目は標準ライブラリを一括してインクルードするものです。C++では多くの機能がライブラリに含まれており、その機能を使うには正しくライブラリをインクルードしなければなりません。例えば cin、cout を使うには #include <iostream> と、string型を使うには #include <string> と記述しなければなりません。制限時間のある競プロではこれは面倒な作業です。#include <bits/stdc++.h> と記述すると標準的なライブラリを一括でインクルードしてくれるのでそのような手間が不要になります。#include <bits/stdc++.h> は Clang（Macに元から入っているg++コマンドも含む）では使用できません。
2行目の using namespace std; は標準的な名前空間を使うように宣言するものです。競プロでは例えば、cin >> N; のような記述をよく見かけますが、本来のC++では「ライブラリ名::クラス名や関数名」のように書くのが作法であり、先ほどの例では std::cin >> N; と書くのが正しいとされています。競プロではこれは面倒なので std:: を省略して書けるように using namespace std; を宣言します。
#include <bits/stdc++.h> と using namespace std; は競プロでは当然のように使われていますが、これらの使用については否定的な意見もありますので、競プロ以外で使用する際にはよく検討してください。
型宣言
型宣言を短縮して書けるように別名を付与します。よく見かけるのは long long を ll とするものです。using でも typedef でもどちらを使っても構いません。
|
1 |
using ll = long long; |
または
|
1 |
typedef long long ll; |
この使用についても賛否両論がありますので、自分なりのやり方を見つけてください。
定数の宣言
次の例は int 型（通常4バイト）で持つことができる最大の値を INF、long long 型（通常8バイト）で持つことができる最大の値を LINF と定義するものです。競プロではこの値が必要になる場面がよくあります。const ではなく #define を使って宣言する方法もあります。どちらでも構いません。
|
1 2 |
const int INF = 0x7FFFFFFF; const long long LINF = 0x7FFFFFFFFFFFFFFF; |
for文の省略など
面倒なfor文を短縮して書けるように定義しておきます。どのようにするのが便利か意見が分かれるところなので自分なりの方法を見つけてください。
|
1 |
#define rep(i, n) for (int i = 0; i < (int)(n); i++) |
または
|
1 2 |
#define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep2(i, s, n) for (int i = (s); i < (int)(n); i++) |
コメント文
コンテストの本番では丁寧にコメントを書く時間などありませんが、筆者の場合は一度やった問題は必ず復習して、必要があればコメントを追加して保存するようにしています。そのときに、問題のURLと参考にした記事があれば記録に残したいのでコメント文もテンプレートに入れてあります。
|
1 2 3 |
//--------------------------------------------------- // 問題 // 解説 |
main() 関数
main() 関数も書いておきます。競プロでは「数Nを読んで、N個のデータを読む」というような問題が多いので、その部分も書いておきます。
|
1 2 3 4 5 6 7 8 9 10 |
int main() { int N; cin >> N; int A[N]; rep(i, N) cin >> A[i]; return 0; } |
データ型、標準関数のテンプレート
C++にはたくさんのデータ型や標準関数が用意されており、うまく使えば競プロの問題が簡単に解けたり、簡潔に書けたりすることも多いです。そのような項目ひとつひとつにもテンプレートを作っておけば本番のコンテストで時間節約になりケアレスミスも防げます。
一例として、次に示すのは vector の使い方について作ったテンプレートです。独立したプログラムとしても動作します。vector の使い方について新しく勉強したらその都度テンプレートにも反映するようにします。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
// 解説 vectorの使い方 // https://qiita.com/ysuzuki19/items/df872d91c9c89cc31aee #include <bits/stdc++.h> using namespace std; #define rep(i, n) for (int i = 0; i < (int)(n); i++) struct Point { int x, y; }; int main() { // vectorの宣言： <型>はclass名なども使用できる vector<int> num = {10, 50, 100}; vector<string> str = {"apple", "bird", "cat"}; vector<Point> point(3, {2,3}); // 初期値付きで宣言する方法（要素数, 初期値） cout << "--- vectorの基本" << endl; //----------------------------- cout << "size = " << num.size() << endl; // サイズ for (auto n : num) cout << n << endl; cout << "size = " << str.size() << endl; for (auto s : str) cout << s << endl; cout << "size = " << point.size() << endl; for (auto p : point) cout << "x=" << p.x << " y=" << p.y << endl; cout << "--- 検索" << endl; //----------------------------- if (find(str.begin(), str.end(), "dog") == str.end()) { cout << "\"dog\" was found" << endl; } else { cout << "\"dog\" was not found" << endl; } if (find(str.begin(), str.end(), "cat") == str.end()) { cout << "\"cat\" was found" << endl; } else { cout << "\"cat\" was not found" << endl; } cout << "--- イテレータ" << endl; //----------------------------- auto it = num.begin(); cout << "begin() " << it[0] << endl; cout << "next of begin() " << it[1] << endl; it++; cout << "next of begin() " << *it << endl; it = num.end(); cout << "back of end() " << it[-1] << endl; cout << "end() " << it[0] << endl; cout << "next of end() " << it[1] << endl; cout << "--- 要素の追加と削除" << endl; //----------------------------- num.push_back(999); // 末尾に要素を追加 for (auto n : num) cout << n << endl; cout << "--" << endl; num.pop_back(); // 末尾の要素を削除 for (auto n : num) cout << n << endl; cout << "--" << endl; num.insert(num.begin()+2, 90); // 要素を挿入 num.insert(num.begin()+3, 91); // 要素を挿入 for (auto n : num) cout << n << endl; cout << "---" << endl; //----------------------------- } |
典型問題のテンプレート
競プロで扱うアルゴリズムは実はあまり多くはありません。典型的な問題なら、そのようなアルゴリズムを適用するだけでほぼそのまま解答になることも多いです。有名なアルゴリズムを使った典型問題を勉強した時は、そのソースコードもテンプレートとして保存してください。
以上、テンプレートについて解説しました。充実したテンプレートを持っていれば鬼に金棒です。問題を解きっぱなしにするのではなく、テンプレートという具体的な形で自分の財産を増やしてください。
コメント