初めに

この記事はCompetitive Programming Advent Calendar 2014の15日目の記事です．

競技プログラミングでは，アルゴリズムをひらめく力や，数学やアルゴリズムの知識量などが強さを決める大きな要素ではありますが， もちろん，プログラミングを使った競技である以上は，コードの実装力が勝敗を分けることもあります． 例えば，ICPC系のコンテストでは，アルゴリズムを考える能力よりも，実装量の多いプログラムをいかにバグなく高速に実装するかが重要な 問題セットが与えられることが時々あります．

競技プログラミングと無縁なプログラマーは，実装力と聞くと， クラスの構造をうまく設計したり，変更に強い美しいコードを実装する能力だと想像する人がいるかもしれません． ですが，プログラミングコンテストに必要な実装力は，そうした保守性や拡張性ではなく， 「目的の処理をシンプルなコードで実装する」ような能力です． そうした実装のために，プログラミングコンテスト界隈には，実務には使われないような，プロコン特有の実装テクニックのようなものが存在します．

この記事では，そうした実装テクニックのようなものを集めてみました．

マクロ

おそらく，プログラミングコンテストに初めて参加して他人のコードを見たときに，まず最初にぎょっとするのは， ソースコードの先頭に大量に書かれている，謎マクロではないかと思います． 例えば，codeforcesで適当にコードを探して見ると，こんなコードが見つかります．

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

#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 (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)

#define inf INT_MAX/3
#define INF INT_MAX/3
#define PB push_back
#define pb push_back
#define MP make_pair
#define mp make_pair
#define ALL(a) (a).begin(),(a).end()
#define all(a) (a).begin(),(a).end()
#define SET(a,c) memset(a,c,sizeof a)
#define CLR(a) memset(a,0,sizeof a)
#define PII pair<int,int>
#define pii pair<int,int>
#define pcc pair<char,char>
#define pic pair<int,char>
#define pci pair<char,int>
#define VS vector<string>
#define VI vector<int>
#define debug(x) cout<<#x<<": "<<x<<endl
#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define MIN(a,b) (a>b?b:a)
#define MAX(a,b) (a>b?a:b)
#define pi 2*acos(0.0)
#define INFILE() freopen("in0.txt","r",stdin)
#define OUTFILE()freopen("out0.txt","w",stdout)
#define in scanf
#define out printf
#define LL long long
#define ll long long
#define ULL unsigned long long
#define ull unsigned long long
#define eps 1e-14
#define FST first
#define SEC second

さすがにこれは極端な例ですが，REPマクロやALLマクロは使ってる人は多いです．

REPマクロは邪悪だとよく言われますが，タイピング量がだいぶ減るので私は重宝しています． たとえば，比較的複雑なDPを書くときは，5重ループなんかがでてきたりしますが， そういうときに，ソースコードの見通しが良くなります．

あとは，下のような典型的なミスを無くすことにも役立ちます．

1
2
3
4

for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; i++) { // i++ -> j++
    }
}

これは，友人が最近使ってるマクロですが，整数やベクトルの宣言と入力をまとめてマクロにしてて危険な香りがします．

1
2
3
4
5
6
7

#define int(x) int x; scanf("%d",&x);
#define lint(x) long long x; scanf("%lld",&x);
#define vint(v,n) vector<int> v(n); rep(i,n) scanf("%d", &v[i]);
#define vlint(v,n) vector<lint> v(n); rep(i,n) scanf("%lld", &v[i]);
#define double(x) double x; scanf("%lf",&x);
#define vdouble(v,n) vector<double> v(n); rep(i,n) scanf("%lf", &v[i]);
#define string(x) string x; cin >> x;

一文字変数，一文字構造体

タイピング量を極限まで少なくするためなのか，変数名を考えるのがめんどくさいのか，一文字変数を好む人がいます．

1

int i,d,o,l,m,a,s,t,e,r;

変数名だけでなく，型の名前も一文字にされることがあります． 例えば自分の幾何問題用ライブラリでは，点や直線がこんなふうに定義されています．

1
2
3

typedef complex<double> P; // Point
typedef vector<P> L; // Line
struct C{ P p; double r; }; // Circle

変数どころか型にまで，なんでこんなに可読性の低い名前にしてるんだと思うかもしれませんが， 一つの理由は幾何ライブラリが使われるICPCのコンテストの事情によるものです． ICPCでは，競技者は25ページの紙に，あらかじめ用意しておいたソースコードを，ライブラリとして印刷して持ち込むことが許されます． そうしたライブラリは，25ページに収めるためにいくらか圧縮しないといけない時があります． また，コンテスト本番でも，幾何の長いライブラリを，紙を見ながら画面に打たないといけないので， 長い型名を何回も打つのは嫌になってきます． こうした理由で，自分の幾何ライブラリはこんな型名になってます．

stdc++.h

これひとつで標準C++ライブラリが全部インクルードできるよ！やったね！

中身: [https://gcc.gnu.org/onlinedocs/gcc-4.6.2/libstdc++/api/a01040_source.html]

1

#include <bits/stdc++.h>

is_uruu

関数の名前なんて飾りです．

1
2
3

bool is_uruu(int y) {
    return y % 4 == 0 && (y % 100 != 0 || y % 400 == 0);
}

負の添字でDP

DPを書くときに，負の添字でアクセスできるような配列がほしい時があります． std::map<int, int>を使ったり，添字に定数を足すという方法もありますが， 以下のようなことをして使う人もいます．

1
2
3
4
5
6
7
8
9
10

int main() {
    const int MAX = 1000;
    int ary[2*MAX + 1];

    // [-MAX, MAX]にアクセスできる!
    int *dp = ary + MAX;

    dp[-1] = 3;
    printf("%d\n", dp[-1]);
}

GCC拡張

標準C++ライブラリではない関数として，GCCはいくつかの便利な関数を用意してくれています． 参考:[https://gcc.gnu.org/onlinedocs/gcc-4.9.2/gcc/Other-Builtins.html#Other-Builtins]

特に便利なのが__builtin_popcount(unsigned)で，これは整数値を2進数で表したときに，1が立っている数を高速に計算してくれます．

ほかに，これはGCC拡張とは違いますが， GCCでalgorithmヘッダをインクルードすると，内部で使っている__gcd(long long,long long)という関数が定義されるので， これをつかうと最大公約数が計算できます

2014/12/15 23:34訂正

• __gcd の 引数はlong longではなくテンプレートで任意の整数型に対して定義される
• __gcd は 現在の実装ではどこにも使われていない

でした．@climpetさんありがとうございます．

dx, dy

プログラミングコンテストの問題では，グリッド上を探索する問題が良く出ます． そういう問題では，ある座標(x, y)から周辺4マスを調べる処理が必要になります． そうしたときには，配列をあらかじめ定義しておくことで， for ループでシンプルに書くことができます．

1
2
3
4
5
6
7
8
9
10
11
12

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int dfs(int x, int y) {
    // (x, y) に対する処理をここに書く

    // 周辺4マスを調べる
    for(int r = 0; r < 4; r++) {
        int nx = x + dx[r];
        int ny = y + dy[r];
        dfs(nx, ny);
    }
}

これを更に発展させるとこんな書き方もできるそうです．

最近, dxy[4] = {0, 1, 0, -1}; にして, int xx = x + dxy[dir], yy = y + dxy[dir+1&3]; とするテクを覚えた.

— 煽らないで下さい (@Mi_Sawa) 2014, 12月 15

dd[5]={0,1,0,-1,0} にして dd[dir] と dd[dir+1] を使ってる．確か8方位でもできた気がするんだけどそっちは覚えてない．

— くりんぺっと (@climpet) 2014, 12月 15

signed main

1
2
3
4
5
6
7
8

#define int long long
signed main() {
    int sum = 0;
    for(int i = 0; i < 1000000; i++) {
        sum += i;
    }
    std::cout << sum << std::endl;
}

32bit整数型に収まると思って書いたコードが，実はオーバーフローしてしまう！ そんなときは，#define int long longですべて解決！

かとおもいきや，int main()までlong long main()に書き換えられてしまうため， コンパイルエラーになってしまいます． そんなときは，int main()をsigned main()に書き換えることで， コンパイルエラーを防ぎつつ，簡単に64bit整数型に書き換えることができます．

終わりに

思いついた実装テクニック（？）をいくつか上げてみました． 自分の知らない変なテクニックがまだまだあると思うのでぜひ教えて下さい．

明日はアイドルマスターのプロ，skyさんの番です！