競技プログラミングテクニック集 in C++

競技プログラミングテクニック集 in C++ === @araiguma --- ### 自己紹介 - アライグマ - (一応) Web班班長 - 最近の趣味はABCの速解き(¬競プロ) --- ### 競技プログラミングとは与えられた問題を解くプログラムを速く書くコンテスト [atcoder](https://beta.atcoder.jp/), ACM-ICPC などなど --- ### 競技プログラミングの実態 (自分のような)一般人が後半の難しい問題を時間内に解くのは厳しい... → いかに前半の問題を速く解くかのTAになりがち --- ### この速解きコンテストを制するには... いかに速く、短くコードを書けるかが重要。 今回はそのためのテクニックを紹介。 --- 注: 競プロ以外で使っても責任は負いません。 --- ### 事前準備編 --- ### bits/stdc++.h 標準ライブラリを一括で読み込んでくれる。gccでしか使えないので注意。 ```cpp= #include <bits/stdc++.h> int main() { // 色々使える。 return 0; } ``` --- ### using namespace std stdを省略できる。 ```cpp= #include <iostream> using namespace std; int main() { cout << "Hello World" << endl; return 0; } ``` --- ### マクロ文字列を置き換えてくれる。 ```cpp= #include <iostream> using namespace std; #define N 102 #define max(a, b) ((a)>(b) ? (a) : (b)) // 関数的なこともできる int main() { cout << N << endl; cout<< max(3, 5) << endl; return 0; } ``` --- ### repマクロ定番。for文を短くかける。 ```cpp= #include <iostream> using namespace std; #define for_(i, a, b) for(int i = (a);i < (b);++i) #define rfor_(i, a, b) for(int i = (b)-1;i >= (a);--i) #define rep(i, n) for_(i, 0, n) #define rrep(i, n) rfor_(i, 0, n) int main() { rep(i, 10)cout << i << endl; return 0; } ``` --- ### 関数名などの省略標準ライブラリの関数名などを省略する。 ```cpp= #include <iostream> #include <vector> #include <utility> using namespace std; #define rep(i, n) for(int i = 0;i < (n);++i) #define pb push_back #define mp make_pair #define ft first #define sd second int main() { vector<pair<int, int>> vp; rep(i, 10)vp.pb(mp(i, i)); rep(i, 10)cout << vp[i].ft << ',' << vp[i].sd << endl; return 0; } ``` --- ### 型の省略マクロ, typedef, usingなどなど ```cpp= #include <vector> #define int long long // int main() のintも入れ替わるので以下の方法で回避 typedef long long ll; template<class T> using V = std::vector<T>; // usingはテンプレート化できる signed main() { return 0; } ``` --- ### 定数初期値などで使える。constなどで書き換えミスを防ぐ。 ```cpp= #include <iostream> using namespace std; const int IINF = 0x3f3f3f3f; // 2倍しても負にならない const long long LINF = 0x3f3f3f3f3f3f3f3fLL; constexpr int INF = sizeof(int) == sizeof(long long) ? LINF : IINF; // #define int long long 対策 const double eps = 1e-15; int main() { cout << 2*INF << endl; return 0; } ``` --- ### cin, cout の高速化そのままのcin, coutはscanf, printfに比べて遅いので同期を切るなどして速くする。 ```cpp= #include <iostream> using namespace std; #define endl '\n' // 実はendlは遅い int main() { cin.tie(0); // cin, coutの同期を切る ios_base::sync_with_stdio(false); // stdioとの同期を切る return 0; } ``` --- ### dx, dy 上下左右を見たい時に便利。実は一つの配列でも実現可能。 ```cpp= #include <iostream> using namespace std; #define rep(i, n) for(int i=0;i<(n);++i) const int dx[4] = { 1, 0,-1, 0}; const int dy[4] = { 0, 1, 0,-1}; const int d[5] = { 0, 1, 0,-1, 0}; int x, y; int main() { cin>>x>>y; rep(i, 4)cout << x+dx[i] << ',' << y+dy[i] << endl; rep(i, 4)cout << x+d[i] << ',' << y+d[i+1] << endl; return 0; } ``` --- ### 実装編 --- ### グローバル変数, 一文字変数変数の名前を短くしてタイプ数を抑える。また、グローバルで宣言すると0で初期化されて便利。 ```cpp= #include <iostream> using namespace std; #define rep(i, n) for(int i=0;i<(n);++i) int N, a[100005]; int main() { cin>>N; rep(i, N)cin>>a[i]; return 0; } ``` --- ### 三項演算子 if文を書く手間が省ける。 ```cpp= #include <iostream> using namespace std; int a, b; int main() { cin>>a>>b; cout << (a>b ? a : b) << endl; return 0; } ``` --- ### 式の値を利用 ```x + 5```や```x == 5```などに限らず、```x = 5```などの全ての式は何かしらの値を返すのでそれを利用する。 ```cpp= #include <iostream> #include <vector> using namespace std; int f[50] = {0, 1, 1}; int fib(int n) { // メモ化再帰 return f[n] > 0 ? f[n] : f[n] = fib(n-1) + fib(n-2); } int main() { cout << fib(40) << endl; return 0; } ``` --- ### ,(コンマ)演算子 ,演算子は左の値を評価し捨てて、その後右の値を評価する。 ```cpp= #include <iostream> using namespace std; int s, n; int main() { while(cin>>n, n)s += n; cout << s << endl; return 0; } ``` --- ### 型変換の利用 bool型のtrueはint型などで1、falseは0になる事や、その逆を利用する。 ```cpp= #include <iostream> using namespace std; int a; int main() { cin>>a; cout << (a%2 ? "Odd" : "Even") << endl; // 0以外の値はtrueになる return 0; } ``` --- ### auto型 C++11では型推論をしてくれる。ただし使える場面は限られてるので注意。 ```cpp= #include <utility> using namespace std; #define mp make_pair int main() { auto p = mp(1, 2); return 0; } ``` --- ### range-based for 多言語でもよくあるやつ。autoを使うと複雑な型でも簡単にかける。 ```cpp= #include <iostream> #include <vector> using namespace std; #define pb push_back vector<int> v; int main() { int n; while(cin>>n, n)v.pb(n); // nが0になるまで for(int i : v)cout << i << endl; return 0; } ``` --- ### 無名関数, ラムダ式引数で渡せたり、多重ループを抜けられたり。 ```cpp= #include <iostream> using namespace std; #define rep(i, n) for(int i=0;i<(n);++i) int main() { int N, a[10][10]; cin>>N; rep(i, N)rep(j, N)cin>>a[i][j]; [&]() { // &や=(コピー)で外の変数もアクセスできる rep(i, N) rep(j, N) if(a[i][j]) { cout << a[i][j] << endl; return ; } }(); return 0; } ``` --- ### 負の添え字 ```cpp= #include <iostream> using namespace std; int main() { const int MAX = 1000; int ary[2*MAX + 1]; int *dp = ary + MAX; // [-MAX, MAX]が使える dp[-1] = 3; cout << dp[-1] << endl; } ``` --- ### まとめ競プロは闇 --- 参考 - [0](https://gist.github.com/rigibun/7905920) - [1](http://torus711.hatenablog.com/entry/20131205/p1) - [2](https://github.com/kurokoji/.cpp-Template/wiki) - [3](http://archive.fo/RhC7T) - [4](http://snuke.hatenablog.com/entry/2015/12/06/005054)