競技プログラミングでの愚かな失敗

競技プログラミングの記事なので，別アカウントから移動してきました (2020/07/25)

競技プログラミングで，よく間違う．C++の言語仕様をうっかりして，ということもあるし，そもそもしょうもない間違いということもある．もちろん愚かだから間違うのだけれど，なるべくなら同じ間違いを何度もしないように，メモをしておく．

以下常に，次のように書いてあるものとする．

using namespace std;
typedef long long int ll;

最小値を求めるループの初期値

vec の最小値 vMin を求めるループを次のように書いて失敗した．

vector<ll> vec;
...
ll vMin = 1e9;
for (ll v : vec) vMin = min(vMin, v);

vec の中の値がすべて $10^9$ より大きかったからである．もちろん注意力が足りないのではあるが，次のように書く癖をつけておけば良かった．

ll vMin = LLONG_MAX;

かと思えば，別の問題では，

x = LLONG_MIN;
...
x += y;

のようなコードを書いて，$y < 0$ だったためにオーバーフローさせてしまった．やはり制約を熟読するのが大事ということか...．

入力を最後まで読まない

数の列が与えられる問題で，列の途中まで読むと答が決まってしまい，後が不要なことがある． つい，次のように書いてしまう．

for (int i = 0; i < N; i++) {
  int x; cin >> x;
  if (some_condition(x)) {
    cout << "-1\n";
    return 0;
  }
  v.at(i) = x;
  ...
}

テストケースが1つなら別に問題ないのだが，Codeforces のように複数のテストケースが与えられる問題で，全体を次のように書いているのに，solve() の中で上のコードを書いてしまった．

int main() {
  int t; cin >> t; 
  for (s = 0; s < t; s++) solve();
}

教訓: なんであれ入力は全部読め．

31以上のビットシフト

次のように書いて失敗した．

  for (int i = 0; i < 60; i++) {
    ll bit = 1 << i;
    ...
  }

もちろん，1 << i でなく，1LL << i でなければならない．

accumulate (に限らないが...)

和を計算してくれる std::accumulate というものがあるというのを見かけて，使ってみた．

  vector<ll> vec;
  ...
  ll vSum = accumulate(vec.begin(), vec.end(), 0);

これはだめで，accumulate(vec.begin(), vec.end(), 0LL) でなければならない．生兵法は大けがのもと．とはいえ，前節「31以上のビットシフト」と同じ話だよな...．学習しない奴．

int vs long long

大きな数は int でなく long long で持たなくてはならない．ということはさすがに間違えないのだが，$10^5$ くらいの数を int x; に代入しておいて，ll y = x * x とやって溢れさせた．何回やったかわからない．学習しない....

これも int vs long long

同じ話だが，関数の戻り値でも失敗した．main の中で

cout << solve() << endl;

と書いておいて，結果は32bitに納まらないことがあり得るとわかっているのに

int solve() {
  ll answer = ...
  ...
  return answer;
}

と書いてしまう．なんなんだろうなあ．

long long でも足りない...

ARC021-C 「増築王高橋君」は，long long でも足りない計算が出てきた.... 厳密には足りないわけでは無いけれど．等差数列の和を足していくコードを書く必要があり，以下のように書いた．

  ll tot = 0;
  ...
  tot += (2 * A + (p - 1) * D) * p / 2;

テストケースが1つだけ通らない．制約をよくよく見ると，$A \leq 10^3$, $D \leq 10^3$, $p \leq 10^8$ なので，2で割る直前の部分が $10^{19}$ を超えることがあり得る．LLONG_MAX は，$9.22\times10^{18}$ くらいなので，オーバーフローしてしまった．次のように書き直して通した．多倍長整数を使っても良かったかもしれない．

  tot += p % 2 == 0 ?
         (2 * A + (p - 1)   * D) * (p / 2) :
         (    A + ((p-1)/2) * D) * p       ;

教訓はなんだろうか? 全部の式で制約をちゃんと見てオーバーフローに気を遣え，ということだろうか? 現実的でない気がする....

long long を過信しない

上と同様な話だが，$ n \leq 10^{18}, m \leq 10^{18} $ という制約で，$ 2^{ (n - 1) * (m - 1) } $ を $ \mod 10^{9} + 7 $ で求めることになった．何も考えずに

  long long n, m;
  // ...
  modint x = power<modint>(modint(2), (n - 1) * (m - 1));

と書いて失敗した．(modint は mod P で計算するクラス．power は べき乗を計算する自作の関数)

   modint x = power<modint>(power<modint>(modint(2), n - 1), m - 1);

としなくてはいけない．

0-indexed と 1-indexed

グラフ問題などで多いのだが，問題文は 1,...,N で与えられているものを 0,...N-1 に直してコーディングすることが多い．例えば，点が1, ..., Nという設定で，入力データは，M本の辺に引き続いて始点，終点が指定されている，と行った場合に，辺だけは1減らして読み込む．この場合，その後の始点，終点を読むときに1減らし忘れて失敗する，という失敗をたびたびする．こんな具合．

  ll N, M; cin >> N >> M;
  vector<vector<ll>> neighbour(N);
  for (ll i = 0; i < M; i++) {
    ll u, v; cin >> u >> v; u--; v--;
    neighbour.at(u).push_back(v);
  }
  ll start, goal; cin >> start >> goal;

つい，start--; goal-- を忘れてしまう．

1,...,N のままでやれば良いのかもしれないが，この方が全体的には楽だと思っている．上の例では，neighbour の2次元めはどのみち 0-indexed になるのだから，1次元目もそうしたい，という気持ちである．方針が悪いかなあ．

ベクトルの値の設定: at と push_back

最初はこう書いていた．

vector<int> vx(N), vy(N);
for (int i = 0; i < N; i++) cin >> vx.at(i) >> vy.at(i); 

事情で pair にすることに変えた．

for (int i = 0; i < N; i++) {
  int x, y; cin >> x >> y;
  v.emplace_back(x, y);
}

vが宣言されていないというエラーになったので，宣言を書き換えた．

vector<pair<int, int>> v(N);

訳がわからないことになった．

最初から pair のつもりで書いていれば，v(N) とは書かなかったと思うが，こういうシークエンスだと，つい間違えてしまう．vector<int> のときも at ではなく push_back を使うように習慣づけるべきだろうか?

添字の範囲

int N; cin >> N;
vector x(N), y(N), p(100000);

のようになっていて

for (int i = 0; i < N; i++) { ... x[i] ... }
for (int i = 0; i < N; i++) { ... y[i] ... }
for (int i = 0; i < N; i++) { ... p[i] ... }

とやって失敗した．最後の N は 100000 と書くべきところ．

単純ミスと言ってしまえばそれまでだが，「ベクトルの要素を全部見る」と思っているので油断したか．

ループの回数

0, 1, 2 で 3 回ループさせるのは，

for (int i = 0; i < 3; i++) {

であって，

for (int i = 0; i < 2; i++) {

ではない．あっっっっっったり前なのだが，なぜか間違えてしまうことがある．この手のはまずデバッグで気づかない．どうしたらよいのやら．

座標圧縮

$\{ (x, y) \mid 0 \leq x \leq X, 0 \leq y \leq Y \} $ に点 $(x_1, y_1), \ldots , (x_k, y_k)$ があるという状況で， 座標圧縮するとなったら，X軸に関しては， $x_1, \ldots , x_k$ だけでなく，当然， $0$ と $X$ も登録しなくてはいけない．これを忘れてしまう．

無駄な入力値

入力に 「$a_i \quad b_i$」(i = 1,..,n) が並んでいて，この意味は「$f(a_i)$の値は $b_i$ 以下」だという． 何の疑問も持たずに

map<int, int> f_bound;
for (int i = 0; i < n; i++) {
  ll x, y; cin >> x >> y;
  f_bound[x] = y;
}

と書いて失敗した．たしかに，「$i \neq j$ ならば $a_i \neq a_j$」という但し書きがなかった が，こういうのは詐欺ではなかろうか ので，ちゃんと気をつけなくてはいけない．

領域確保にも時間はかかる

十分間に合っているつもりなのにTLEするコードを一生懸命デバッグして，どのループもそんなに時間はかかるはずがないのに... と思っていたら，下のようなコードがあった．

for (int i = 0; i < n; i++) {   // n は 2e5 まで
  vector<int> count(k);     // k は 2e5 まで
  ...
}

そりゃ無理ですね．

この後で count[x] として現れるxの種類は十分少なかったので，vector<int> でなく map<int, int> を使うべきところだった．

小数点以下の桁数

答が小数になる問題で，何も考えずに次のように書いたら，小数点以下5桁くらいしか表示されなくてだめだった．

  double ans = ....;
  ...
  cout << ans << endl;

これより前のどこかで次のように書いておけば良い．

  cout << setprecision(20);