競技プログラミング for beginners! ～C++実装テク編～

少し早いけど，メリークリスマス！
この記事は中高生プログラマ Advent Calendar 2015 - Adventarの22日目として書かれたモノです。

自己紹介

競技プログラミングを主にやってる高校生。
人生のバイブルは天才バカボン。「競プロerなら蟻本だろ。」って怖い人に突っ込まれそうですね。蟻本持ってないから許せ。

Twitterを見ればどんな人か分かると思いますので詳しいことは省きます。
もし僕についてもっと知りたい人がいたら声をかけてくれれば1時間でも2時間でも話しますので，遠慮せずに。
twitter.com

前置きと諸注意

タイトルに実装テク編と書いたものの，アルゴリズム編やデータ構造編を書く能力も気力もないので，あまり過度な期待はしないほうがいいです。
こうやってタイトルに書いておくことで「ググられビリティ」みたいなのが高まる感覚ない？僕はあるよ。

「こういう書き方もあるんだな」っていう程度の参考にしていただければ結構です。
競プロ出来ない奴が書いてるからもしかしたら間違えがあるかもです。その時はコメントかTwitterで教えてください。

また，この文章を読んでいるとき、画面をスクロールするためにマウスを使うと手の油分や汗が付着する可能性があるので、ソレが気になる方は手袋をすると良いでしょう。使い捨てのゴム手袋などが理想的ですね。
スマホで読んでいる人はスマホ対応型手袋を使いましょう。
この文章を必要ないなと感じて読み飛ばした人は論理的に考えて行動出来る人だと思うので競プロ強い人です。
そうじゃないよく読んでいた人は問題文を誤読する心配が無さそうなのでやっぱり競プロ強い人です。

この記事が対象にしている人

・C++でループ，条件分岐ができる人
・C++以外の言語でプログラミング経験のある人
・競プロerのコードを見てギョッとした人

上記以外でプロの方はブラウザの戻るボタンを押してください。怖いんで。。。
そうじゃない初心者は入門サイトなどを一通り読めばこの記事は問題なく読めると思います。
C++入門
C++入門～bituse～
競プロにおいてはそこまでクラスとか仮想関数とか気にする必要ないかもですね。
知っていると書き方の幅が広がるのは確かですが。

そろそろ競プロの話，しません？

しましょう。

変数名

タイプ数や時間短縮のための1文字変数がやたらと多い。

例

int t; //時間
int p; //ポイント
int r, h, y; //平面図形，座標が関わってくる問題で縦，y座標を表す。
int c, w, x; //上と同じく横，x座標を表す。

確かに楽ですが，何を表したモノなのか分かりにくくなるのでバグの原因になることがある。

マクロ

for構文

REPマクロなどはタイプ数がかなり減る。

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)

int main(){
   REP(i, 10){...} //i=0～i=9までのループ
   FOR(i, 3, 10){...} //i=3～i=9までのループ
   REPR(i, 10){...} //i=10～i=0までのループ
}

INF

INFでものすごく大きな数や，-INFでものすごく小さい数を表すことができます。
INF，-INFで初期化しておくことで最小値や最大値を求める時に下のような書き方ができる。

#define REP(i, n) for(int i = 0;i < n;i++)
#define INF 999999999

int main(){
   int a[4]={2, 4, 6, 8};
   int mini=INF, maxi=-INF;

   REP(i, 4){
      mini=min(mini, a[i]);
      maxi=max(maxi, a[i]);
   }
}

上のプログラムでminiには最小値である2が，maxiには最大値である8が代入されることになる。

またINFを32bit整数型の最大値などあまりに大きすぎる数にしていると以下のような時に正しく動かなくなる。

#define INF 2147483647

int main(){
   int mini=INF, tmp=1;
   mini=min(mini+tmp, 0);
}

まあ当たり前と言えば当たり前なんだけどね…
私もコレでバグってからはおとなしく999999999にしてます，はい。

#define INF 1145141919

コレでは臭すぎるので論外。

long long

数字が32bitに収まらないなら64bitにすれば良いじゃない。
そんな時にはlong long。
これも楽しましょう。

#define llong long long

int main(){
   llong n=1145141919810;
}

llとかしちゃう人もいます。

dy, dx

座標上を探索する時に便利。

int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
   int ny, nx; //今いる座標。
   REP(i, 4){
      int ty=ny+dy[i];
      int tx=nx+dx[i]; //探索対象にする座標。
   }
}

斜めに移動できるとかいう条件があればその都度足していけば良い。

bits/stdc++.h

#include <bits/stdc++.h>

僕も最近知ったんだけどこれでC++の標準ライブラリが全部インクルードできるんだと。
すごい時代になったもんだよ，まったく。
え？使わないモノをわざわざインクルードしたくないって？
お前育ち良いね。

STLのデータ構造

vector, set, map, queue, stack, priority_queueといろいろあるよ！うれしいね！！
使い方なんてその都度ググっていけば良いよ。

stackとかqueueとかなんだよって人はデータ構造について勉強しましょう。
リンク先のコレクションってところです。
アルゴリズムとデータ構造 | ++C++; // 未確認飛行 C

STLのアルゴリズム

sort, stable_sortなどこっちもいろいろあるよ！よかったね！！

sortとかstable_sortとかなんだよって人はアルゴリズムについて勉強しましょう。
リンク先のアルゴリズムってところです。
アルゴリズムとデータ構造 | ++C++; // 未確認飛行 C

他のSTLアルゴリズムをもっと詳しく知りたいって人は下のリンク先を見ておくと良いでしょう。
標準テンプレートライブラリ(STL) アルゴリズム - Qiita
共通アルゴリズム - STL
競プロでよく使うのはsort, upper_bound, lower_bound, min, max, swapあたりでしょうかね。

長くなったし疲れたしそろそろ終わりにしたい。

そうしましょう。
最後に，僕が競プロ特有な書き方を覚える時に使用したサイトや方法と僕の競プロ用テンプレートを置いておきます。

AtCoder (アットコーダー)
日本人で競プロやってる人はほぼみんな知ってるであろうAtCoder。
終わったコンテストでは他人のソースコードを見ることができるので参考にするのが良い。

競技プログラミング特有の変な実装テク // ichyo.jp
この記事の内容と結構かぶっているところがあるのは僕がこのいちょう(@ichyo)さんの記事を参考にAtCoderなどでソースコードを読んでいたからです。
僕よりも数百倍詳しく説明してくれてます。

競技プログラミング Wiki*
C++だけじゃなくJavaについても書いてあるので，Javaの経験ある人はココ見てみると良いかも。

～競プロ用テンプレート～

#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(){

}