この記事はCompetitive Programming Advent Calendar 2015の６日目の記事として書かれました。
この記事は、C++初心者が頑張って編み出した、C++初心者の競技プログラマ向けの実装テクニックを紹介するものです。
筆者自身がC++に詳しいわけではないため、仕組み等の解説は避け、「こう書けばいい感じに動くよ」みたいな部分だけを書いていきます。
「競プロでの応用例」という点に注目して読んでいただければと思います。
range-based for
これはよく知られていると思います。以下のように書くとvectorとかmapとかを舐められるやつです。
for (型 変数名 : 舐める対象)
使用例です。
void printVector(vector<int>& d) { for (int a : d) printf("%d\n", a); } void printSet(set<int>& d) { for (int a : d) printf("%d\n", a); } void printMap(map<int,int>& d) { for (pair<int,int> a : d) printf("%d %d\n", a.first, a.second); }
特にmapを舐める操作が簡潔に書けて良いですね。
autoという型を自動で判断してくれる便利なやつを使うとさらに楽になります。
void printMap(map<int,int>& d) { for (auto a : d) printf("%d %d\n", a.first, a.second); }
書き換えがしたくなった場合は、参照で舐めることもできます。
void twiceVector(vector<int>& d) { for (int& a : d) a *= 2; } void twiceMap(map<int,int>& d) { for (auto& a : d) a.second *= 2; }
range-based forをグラフの問題で使うときは注意が必要です。
vector<int> to[MAX_V]; // 木を舐める void dfs(int v, int dist, int p=-1) { printf("%d : %d\n", v, dist); for (int u : to[v]) if (u != p) dfs(u, dist+1, v); }
このようなケースでは便利で問題ないのですが、辺にコストがつくと普通のforで書かざるを得なくなります。
（いい方法知ってたら教えてください）
vector<int> to[MAX_V]; vector<int> cost[MAX_V]; void dfs(int v, int dist, int p=-1) { printf("%d : %d\n", v, dist); for (int i = 0; i < to[v].size(); ++i) { int u = to[v][i]; if (u != p) dfs(u, dist+co[v][i], v); } }
range-based forで途中まで書いてコストがあることに気づいて書き直す、なんてことがないように気をつけたいものです。
lambda式
やばそう、というくらいにしか思ってない人もいるんじゃないかと思いますが、意外と競プロでも便利だったりします。
基本形
lambda式とは、超簡単に説明すると、関数みたいなやつです。
基本的な構文は以下の通りです。
[](引数) { 処理 };
例えば以下のように使えます。
void solve() { auto mod2 = [](int x) { return x % 2;}; printf("%d\n", mod2(2015)); }
この例だと、関数内で関数が作れるという嬉しさ（嬉しいかどうかは知らない）しかありません。
補助関数
ここからが本領発揮です。
まず、「[]」を「[&]」にすることで、スコープ内の変数に自由にアクセスできるようになります。
スコープって何？っていう人はスルーして下の例を見てください。多分スコップとスープを足して２で割ったようなやつです。
例題：
0に以下の操作を何回か行ってNにしたいです。最小何回でできるでしょう？ ・+1する ・-2する ・2倍する ・2乗する
要するに、遷移の種類がたくさんあるBFSです。
lambda式を使うと結構綺麗に書けます。
int solve(int n) { vector<int> dist(n+1, INF); queue<int> q; auto add = [&](int x, int d) { if (x < 0 || x > n) return; if (dist[x] != INF) return; dist[x] = d; q.push(x); }; add(0, 0); while (q.size()) { int x = q.front(); q.pop(); add(x+1, dist[x]+1); add(x-2, dist[x]+1); add(x*2, dist[x]+1); add(x*x, dist[x]+1); } return dist[n]; }
[&]にすると、distやqにアクセスできるようになるという点がポイントです。
（この例だと頂点と距離のペアをqueueに突っ込んで行って、popしたときにいろいろ判定するという方法もあります）
（↑ダイクストラだと、queueに入れる前にチェックしないと定数倍がわりと重くなります）
比較関数
さて、lambda式の利用法として「比較関数」は外せないでしょう。sortの比較関数とかでlambda式を使うと良い感じです。
void sortRect(vector<pair<int,int>>& rect) { sort(rect.begin(), rect.end(), [](P a, P b) { return a.first*a.second > b.first*b.second; }); // [](const P& a, const P& b) とすると少し速くなります } void sortByValue(const vector<int>& value) { vector<int> id; for (int i = 0; i < value.size(); ++i) id.push_back(i); sort(id.begin(), id.end(), [&](int a, int b) { return value[a] < value[b]; }); for (int a : id) printf("%d : %d\n", a, value[a]); }
１つ目は、長方形（ペアで２つの辺の長さを持っている）を面積の降順にソートしています。
２つ目は、添字の方をvalueの昇順にソートしています。「[&]」が活きていますね。
lambda式が一番輝くシチュエーションは、個人的にはSuffix Arrayではないかと思っています。
struct SA { string s; int n; vector<int> id, rank; void construct() { s += '$'; n = s.size(); id = rank = vector<int>(n); vector<int> tmp(n); rep(i,n) id[i] = i, rank[i] = s[i]; int k; auto comp = [&](int i, int j) { if(rank[i] != rank[j]) return rank[i] < rank[j]; int ri = i + k < rank.size() ? rank[i + k] : -1; int rj = j + k < rank.size() ? rank[j + k] : -1; return ri < rj; }; for (k = 1; k < n; k<<=1) { sort(id.begin(), id.end(), comp); tmp[id[0]] = 0; for (int i = 1; i < n; ++i) tmp[id[i]] = tmp[id[i-1]] + comp(id[i-1],id[i]); rank = tmp; } } };
ちなみに、classの代わりにstructを使うとpublicを書かなくてもいいので楽です。（お行儀は悪いですが）
多重ループbreak
さて、最後にちょっと変わった使い方も紹介したいと思います。
ずばり、多重ループを抜けるときに使えます。
多重ループを抜ける方法には、
・if (~) breakをたくさん書く
・i,j,kとかを書き換えてループの終了条件を全部満たすようにする
・gotoを使う
などがありますが、個人的にはどれもなんだかモヤッとします。
そこでラムダ式を利用します。
比較も兼ねて全部の例を書きます。
// if (~) breakをたくさん書く for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { ++cnt; if (cnt >= m) break; } if (cnt >= m) break; } if (cnt >= m) break; } // i,j,kとかを書き換えてループの終了条件を全部満たすようにする for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { ++cnt; if (cnt >= m) i = j = k = n; } } } // gotoを使う for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { ++cnt; if (cnt >= m) goto LABEL; } } } LABEL: // lambda式を使う [&] { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { for (int k = 0; k < n; ++k) { ++cnt; if (cnt >= m) return; } } } }();
多重ループを「[&] { ~ }();」で囲って、breakの代わりにreturnを使うだけです。
若干トリッキーな記法なので、少し解説します。
[&]() { ~ }
↓ 引数を省略（引数がない場合は省略できる）
[&] { ~ }
↓ このlambda式を関数呼び出しみたいに呼び出す
[&] { ~ }()
という感じです。
コメントアウトの小技
おまけです。
範囲コメントアウトをするとき、いちいち4文字付けたり消したりするのは面倒ですよね。
これを編集距離１でtoggleする方法を紹介します。
/* コメントアウトされている //*/ ↑ ↓ //* コメントアウトされていない //*/
楽ですね！
応用編もあります。
/* 操作１ //*/ 操作２ ↑ ↓ //* 操作１ //*/ 操作２
こう書くと、操作１と操作２をtoggleできるようになります。
最近はエディタのショートカットを使うようになったので使わなくなりましたが。。
まとめ
以上、どうだったでしょうか？
参考になった点が少しでもあれば幸いです。
C++11には他にもinitializer listなどの便利機能があるので興味があればチェックしてみてください。
なんか、僕が書く感じのジャンルじゃなさそうに見えますが、是非紹介したかったので書いてみました。
僕はあまり処理能力が高くないので、見通しの悪いコードを書くとすぐにバグを入れてしまいます。
なので、いかにコードの見通しを良くするかということをたまに考えていたりします。
その結果、この記事が生まれたという感じでしょうか。
明日は、sigma425さんの「何も決まってないです。」です。楽しみですね！
