競技プログラミングで陥りやすい言語仕様の罠

筆者: qnighy

競技プログラミングでは手続き型言語として必要な最低限度の言語仕様さえ覚えておけば問題ないとされることが多い。

その一方で、ある種の特殊な言語仕様を知らないことによって特殊なバグに悩まされることも少なくない。

そこでここでは、そのような競技者の嵌りやすい罠を見つけ次第挙げていきたい。

CとC++の配列初期化の罠

int array[128] = {0};

これはC言語において一般的な配列の初期化である。これは簡単に言ってしまえば、arrayの中身を全て0で初期化する。

しかしこれを次のようにしてはいけない。

int array[128] = {-1}; // バグの原因！

これは 最初の項目だけを -1で初期化する。

詳しい理由は 本の虫: 多くのプログラマは言語を表面的な理解だけで使っている などを参照してほしい。

演算子の優先順位

特にビット演算が関係する計算式には注意すること。

int dp[ 1<<MAX_N + 5 ]; // バグの原因！

while( a&b == 1 ) {} // バグの原因！

boolean型が特別視されるJavaでは後者は見つけやすいが、前者は発見できない。

注意が必要である。

参考: C++ 演算子の優先順位 [C++ Reference]

CやC++の特別な変数名

CやC++ではアンダースコア(_)で始まる変数名は予約語と同様の扱いであり、それがユーザー定義の識別子として扱われることは保証されない。

まさか実際に当たるとは思わないものだが、実際に当たってしまった人がいたのでここに書こう。_endである。

int _end = 0; // gccが定義するシンボル

Local Storage の空きメモリを取得する を参照。

これによってプログラムが非常に意味不明な挙動をし、原因を把握するのに時間がかかったケースがあったので、ぜひ気をつけて頂きたい。

scanfの罠(1)

scanf("%c", &c); // 空白も一文字とみなすから注意！
scanf("%s", s); // 空白の直前で打ち止めするので注意！

次のようにするといいことが多い。

scanf(" %c", &c); // 空白を飛ばしてから読む
scanf("%[a-zA-Z 0-9_]", s); // アルファベットと数字とアンダースコアとスペースが出てくる間は読み込む

scanfの罠(2)

double d;
float f;
scanf("%f%lf", &f, &d); // fはfloat, dはdouble
printf("%f%f", f, d); // fはdouble (floatは自動でdoubleに変換される。)
printf("%lf", d); // これはC99より前は非標準

この非対称な挙動はあまり知られていない。最後に述べた非標準な挙動がサポートされることが多いからである。

strlenはO(n)

Cの文字列の仕様から明らかではあるが、strlenはO(n)である。

for(int i = 0; i < strlen(s); i++) {} // オーダー的に危険