コンテスト系での注意事項
忘れないようにコンテスト系での注意事項をまとめていきます。
コンテストに参加するときの注意事項ではなく、コンテストでのコーディング中に気をつけることなのでお間違えなく。
あと基本的に私の備忘録なので他の方は多分こんな物見なくてもいいかと・・・
※こちらも随時更新の予定・・・
※2010/12/29 更新
問題文をよく読むこと
当たり前のことですけどね。
ただ、コンテスト中は焦っていくつかの制約事項や条件を見落としてしまいがちなのでよく読みましょう。
http://codeforces.com/contest/41/problem/D
自分はこの問題でやってしまいました。
2行目の出力に開始地点ではなく終了地点を出力してました。。。
計算時の型に注意
計算時の型や暗黙の型変換などにより意図しない結果になることが多々あります。
一番の例が整数型同士の割り算ですね。
int a = 3; int b = 2; double d = a / b; // d == 1 double e = 3 / 2; // e == 1
他の例としては非負数と負数の比較もあります。
unsigned int u = 10; if( u < -1 ) cout << "error!" << endl; // 実行される
このようにはっきりと出る場合はあまりなく、むしろこういうのは複雑な式の中に出てきたりするので注意です。
例えば非負数なんて自分では使わなくてもstring::size()やvector::size()などはsize_t型やsize_type型になっており、実体はunsignedだったりするので気をつける必要があります。
出力時の型に注意
出力するときの型に注意しましょう。
型によって整形のされ方が違うため、意図しない出力フォーマットで出されることがあります。
http://codeforces.com/contest/48/problem/C
自分はこれでやってしまいました。
途中までの計算をdoubleでやって最後の出力もそのままdoubleでやったために、値が大きいときに 1e+06 みたいな出力を出されたためにWAになったようです。
浮動小数点数の誤差
除算を行うときは基本的にdoubleなどの浮動小数点数を使いますが、浮動小数点数を使うときは誤差に注意が必要です。
二分探索などで繰り返し計算を行うとある値を得られますが、その値には誤差が含まれていることを考慮する必要があります。
例えば出力するときには1.50000と出力されても実際の内部データは1.49999とかになってる可能性が十分にあります。
参考:http://ideone.com/92Dp4
そのため、この誤差を修正する必要があります。
この誤差の修正にはすごく小さい数を足して後は必要に応じてある桁以下は切り捨てるとか、差を取ってすごく小さい数未満であれば等しいとみなすなどの処理を行います。
また、当然ながら==は使えません。
#例外はあると思いますが、結論として混乱の元になるだけなので浮動小数点数を使うときは比較のみで行う方が無難です。
以下に使えそうな関数を列挙しておきます。
- abs
- 絶対値を取る関数
- int、long版
- float、double、long double版
- ceil
- 天井関数(引数を下回らない最小の整数値/引数以上の最小の整数値)
- float、double、long double版
- floor
- 床関数(引数を上回らない最大の整数値/引数以下の最大の整数値)
- float、double、long double版
四捨五入したければ0.5を足した後floorを使えばいいと思います。