前置き
これは、Competitive Programming Advent Calendar Div2013, 第 5 日の記事です。
記事の内容はタイトルの通り、アルゴリズムではなくコーディング自体に関するテクニック集です。（おそらく）競技プログラミング界隈ではこういった知識についてのまとまった資料が少なく、他の参加者のコードを見て盗まなければならないというのが現状だと思います。当ブログでも、テクニカルな書き方をしたコードを特に説明せずに掲載しているので、わたしがよく使っているものをまとめてみようと思いました。
この記事の内容を実践することで、例えば次のような効果があります。（個人の感想です）
- コード量が減少し、すっきりまとまったコードになってうれしい
- コードの意味が分かりやすくなり、デバッグしやすくなってうれしい
- Challenge / Hack の際に変なコードでも読めるようになってうれしい
- コードがカッコよくなってうれしい（超重要）
もちろん、慣れないと可読性を損なう可能性がありますし、ここでまとめる書き方こそが優れているなどと言うつもりはありません。しかし、こういったテクニックを使ってコードを書くのは正直楽しいです。気に入ったものがあれば是非活用して、カッコいいコードを書いてみてください。
小手先の技
ちょっとした書き方の工夫でどうにかするテクニックたちです。
double へのキャスト
整数同士の除算結果は整数になりますが、実数として除算したい場合があります。その場合、素直に書くと明示的キャストを用いて以下のようになります。
(double)a / b
ところが、int 型と double 型との演算は double に暗黙変換されるので、a を double にキャストする代わりに 1.0 を掛けることで同じ結果が得られます。また、1.0 は 1. と書けます。すなわち、次のようなコードにできます。
1. * a / b
return 文を条件演算子で
条件によって二つの値の内いずれかを return するコードは if 文を用いて次のように書けます。
if ( cond ) { return a; } else { return b; }
条件演算子を用いることで、このようになります。
return cond ? a : b;
変数名を工夫する
特に DP で顕著なのですが、ループ変数名を適当に i, j, k, ... とか書くと分かりづらくなる場合があります。そのループ変数が何に関するループで回っているのかの情報を変数名にもたせることで可読性を上げることができます。例えばわたしは、bit DP で部分集合を列挙するループ変数は s という変数名にしています。
ブロック化
処理をブロックの中に入れることで、スコープを制限して変数名の衝突を防ぐとともに、視覚的に分かりやすいコードにできます。
{ // 処理 A
// 何かする
}
{ // 処理 B
// 何かする
}
実数の比較
実数同士の比較は誤差を吸収するため極小の値 EPS を加減算して調整する、という話はよく知られていると思います。このとき、比較演算子は <= でも < でも（ほぼ）変わりません。しかし、実現したい比較に対応した演算子を書いておくことで、EPS を足すのか引くのか分かりやすくなります。
例えば、<= 演算子の場合は 左辺＝右辺 も許容されるということが明確になるので、右辺に余裕をもたせるため EPS を足せば良いことが分かりやすくなります。同様に、< 演算子の場合は左辺は右辺より厳密に小さいので、右辺から EPS を引けばよいことが分かりやすくなります。
a <= b + EPS a < b - EPS
テンプレート型を明示的に指定
例えば int 型の値 a と vector v があったときに、以下のコードはコンパイルが通りません。vector::size の戻り値は int 型ではないので型が合わないからです。
std::max( a, v.size() )
v.size() を int にキャストしてもよいのですが、std::max の型を明示的に与えることでも解決できます。
std::max<int>( a, v.size() )
論理演算の結果をそのまま使う
何らかの条件を満たす組み合わせを一つずつ数え上げるコードは普通に書くと次のようになります。
if ( a == b )
{
res++;
}
ところが、bool 型の値は 0 / 1 であるので、次のように書いても同じことになります。
res += a == b;
二重否定
値を二重否定 ( !!a ) することで非ゼロは 1 に、ゼロは 0 にすることができます。C 言語由来の関数が bool ではなく int を返してくる*1ので前項のようなことをする場合には必要になります。
res += !!( a % m )
切り上げ整数除算
a / m を端数切り上げで計算する場合、予め a に m - 1 を足しておくと上手くいきます。
( a + m - 1 ) / m
四捨五入
実数型の値に 0.5 を足してから整数型にキャストすると四捨五入されます。小数部分が 0.5 未満のとき整数部分は変わらず、そうでないとき整数部分が 1 増えるからです。
(int)( a + 0.5 )
条件演算子を左辺に
条件演算子の結果のところを変数にした場合、それは左辺値になります。つまり、代入等の対象にできるので以下のようなコードが書けます。
( i < x ? a : b )++;
vector<int> v1, v2;
( i < x ? v1 : v2 ).push_back( i );
入力の終わりまで処理
入力の終わりが特別な値*2で与えられず、「入力の終わりまで処理せよ」という問題がたまにあります。そのような問題では、入力が終わったどうかを知る必要があります。
cin は入力に失敗したときに内部状態が変化します。状態を調べるメンバ関数があるのでそれを呼び出すことで入力が終了したことを知ることができます。さらに、bool へのキャスト演算子が定義されているので、cin を bool として評価すれば正常な状態にあるかどうかを知ることができます。また、>> 演算子の評価結果は左辺のストリームへの参照です。これを while の条件式部分に書くことで「入力が終わるまでループ」を実現できます。
while ( std::cin >> hoge ) { // do anything }
空白を含めた一行を読み込む
string への >> 演算子は、空白文字が来るとそこで止まってしまいます。空白を含めた一行（改行文字まで）を読み込みたいときは、std::getline() を使って次のように書きます。
std::string s; std::getline( std::cin, s );
getline は第一引数に渡したストリームへの参照を返します。なので、前項のように while 文の中に書いて入力の最後まで読み取ることもできます。
余計な文字を読み飛ばす
ストリームから >> 演算子で string に読み込むとき、それに続く改行文字は残っています。大抵は問題無いのですが、getline を使う場合は注意が必要です。getline は改行文字までを読み込むので、string への >> による読み込みに続けて getline を使うと読み込んだ結果が空文字列になってしまいます。ignore というメンバ関数を使うと次の一文字を読み捨てるので、余計な改行文字を捨てることができます。
cin.ignore();
複数の値を空白区切りで一行に出力
複数の値を空白区切りで一行に出力する場合がしばしばあります。インデックスを見て 0 でないときに if 文で空白を出力してもよいのですが、以下のようにも書けます。
vector<int> as( 10 ); // パターン 1 for ( int i = 0; i < as.size(); i++ ) { cout << as[i] << ( i + 1 < as.size() ? ' ' : '\n' ); } cout << flush; // パターン 2 for ( int i = 0; i < as.size(); i++ ) { cout << ( i ? " " : "" ) << as[i]; } cout << endl;
STL を使う
C++ の STL ( Standard Template Library ) には、多くの便利な機能が含まれています。特に、各種コンテナと algorithm ヘッダに含まれる関数群は重要です。STL 自体に関する資料は探せばいくらでも出てくると思いますし、全てを列挙するのは大変なので、ここでは競技で使えるいくつかのテクニックのみに焦点を当てます。
文字列の連結
一時期の TopCoder では、分割された文字列で入力が与えられる形式の問題がよく出題されていました。実は、std::accumulate を使って文字列を連結することができます*3。accumulate は（指定しなければ）+ 演算子を用いて計算をします。また、stirng には文字列連結をする + 演算子が定義されています。accumulate は + 演算子の左辺の型を第三引数によって決定するため、空文字列を表す string オブジェクトを第三引数に渡せば、範囲内の文字列が全て連結されます。
vector<string> ss; // 入力で受け取った string の配列
string s = accumulate( ss.begin(), ss.end(), string() );
C++11 の機能を使う
C++ の新バージョンである C++11 が TopCoder でも使えるようになりました。C++11 で追加された機能を使うとずいぶん楽にコーディングできるようになります。C++11 も STL と同じくいくらでも資料があると思うので、特にオススメなものを数点紹介するに留めたいと思います。
auto 型
iterator が返ってくる STL 関数は多くありますが、iterator の型名は非常に煩雑です。C++11 では、代入時初期化する変数の型を auto と書くことで、右辺から型推論できます。
auto it = find( v.begin(), v.end(), a );
range-based-for
STL コンテナの中身に対してループしたい場合、従来は iterator を使ってループしていました。auto を使えば簡単に書けますが、iterator 自体は必要無いとき、毎回デリファレンスするのは面倒です。
C++11 では range-based-for という所謂 foreach 文が導入されました。範囲の中身を一つずつ変数に代入してループすることができます。range-based-for は begin() / end() を備えるコンテナの他、生配列に対しても使うことができます。
vector<bool> v( 10 ); for ( auto &i : v ) { // 何かする }
ラムダ式
関数オブジェクトを引数にとる STL 関数は多いですが、従来の C++ で関数オブジェクトを作るのはかなり面倒です。離れた場所で定義すると読みづらいし、バインダなどで作ると正直分かりづらいです*4。
C++11 では無名関数オブジェクトを生成する構文が導入されています。これを使うと、例えば文字列を長さの昇順にソートするコードは次のように書けます。
vector<string> ss; sort( ss.begin(), ss.end(), []( const string &s1, const string &2s ){ return s1.size() < s2.size(); } );
GCC 拡張
多くのオンラインジャッジがコンパイラとして GCC を採用していて、GCC の拡張が使えたりします。特に便利な関数をいくつか紹介します。
__gcd
最大公約数 ( Greatest Common Divisor ) を求める関数です。ユークリッドの互除法をライブラリ化しておいて貼り付けてもよいのですが、それすら面倒になったらこちらをどうぞ。
__builtin_popcount
引数で渡した値のビット表現に於いて、立っている bit がいくつあるかを数えてくれます。64 bit の値の場合は __builtin_popcountll です。
__builtin_clz
引数で渡した値のビット表現に於いて、立っている bit の内最も上位のものの左にいくつの 0 があるかを数えてくれます。つまり、ビット表現での Leading Zero を数えます。64 bit の場合は前項と同じくサフィックス ll を付けます。0 には使わない方がよかったような気がします。
__builtin_ctz
clz の親戚です。こちらは末尾側の 0 、すなわち Trailing Zero を数えます。
最後に
いかがでしたでしょうか？ 思ったより数があったのでわたし自身驚いています。内容に於いてはできるだけ嘘を書かないよう心がけましたが、間違い等あればご指摘お願いします。
それでは、お読みいただきありがとうございましたっ！
