競技プログラミング テクニック集 in C++
===
@araiguma
---
### 自己紹介
- アライグマ
- (一応) Web班 班長
- 最近の趣味はABCの速解き(¬競プロ)
---
### 競技プログラミングとは
与えられた問題を解くプログラムを速く書くコンテスト
[atcoder](https://beta.atcoder.jp/), ACM-ICPC などなど
---
### 競技プログラミングの実態
(自分のような)一般人が後半の難しい問題を時間内に解くのは厳しい...<!-- .element: class="fragment" data-fragment-index="1" -->
→ いかに前半の問題を速く解くかのTAになりがち<!-- .element: class="fragment" data-fragment-index="2" -->
---
### この速解きコンテストを制するには...
いかに速く、短くコードを書けるかが重要。<!-- .element: class="fragment" data-fragment-index="1" -->
今回はそのためのテクニックを紹介。<!-- .element: class="fragment" data-fragment-index="2" -->
---
注: 競プロ以外で使っても責任は負いません。
---
### 事前準備編
---
### 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)
<!-- STL(データ構造(map, set, etc)や関数 [参考](https://qiita.com/shirakawa4756/items/f4cc65c6b2b412b10c0c)(sort, unique, etc)), 初期化リスト, 個別やローカルでのusing宣言, istream_iterator, for_each, 構造体(class), 可変長(テンプレート)引数 [参考](https://qiita.com/leon-joel/items/81415c1ef355c6246280), inline関数, 参照, ユーザー定義リテラル(UDLs), 構造化束縛 [参考](https://qiita.com/yumetodo/items/68f58de43094519ae899) , etc についてもそのうち書きたい -->
{"metaMigratedAt":"2023-06-14T17:58:42.000Z","metaMigratedFrom":"Content","title":"競技プログラミング テクニック集 in C++","breaks":"true","contributors":"[{\"id\":\"f97f2aa2-65a0-4d38-b120-1d6338f4e765\",\"add\":7410,\"del\":1338}]"}