c++でオーバーフローが起きる理由がわからない

Question

c++のint型におけるオーバーフローについての質問です。

この問題に対して以下のようなコードを書いたところ、WAと判定されました。

#include <iostream>
using namespace std;
 
int main(){
  int N, A[200001]; // Aは商品価格を格納するための配列
  int B[5]; // Bは価格別の商品の個数を記録する配列
  cin >> N;
  for(int i=0; i<N; i++) cin >> A[i];
  for(int i=0; i<5; i++) B[i]=0;
  for(int i=0; i<N; i++){
    B[A[i]/100]++;
  }
  cout << B[1]*B[4]+B[2]*B[3] << endl;
}

解答例を確認したところ、「オーバーフロー回避のため64ビット整数を使う」と書いてあったため、 int B[5]の部分を long long B[5]に変えたらACになりました。

問題の制約条件から、配列Bの要素は最大でも200,000にしかならないため、32ビット整数であるint型でもオーバーフローは起きないと考えていました。どうしてこの状況でオーバーフローが起こり得るのか教えていただけると幸いです。

Answer 1

問題になるのは、以下の部分です。

  cout << B[1]*B[4]+B[2]*B[3] << endl;

B[1]*B[4｣やB[2]*B[3]は、100,000 * 100,000 があり得て、その場合、オーバーフローします。

その為、この部分のキャストだけでも、BAになったと思われます。

Comments

[miagolare]

そっちが問題でしたか！
確かに言われてみればその通りですね。盲点でした。
ご回答ありがとうございました。

Answer 2

整数の二項演算の結果は原則としてその二項の大きい側の型が結果の型であるというルールです。 (実際にはもっと複雑なルールが色々あります。)

つまりこの場合は B[1]*B[4] という式の型もまた int です。 200000×200000=40000000000 は int (32bit) に収まりませんからオーバーフローになってしまいます。 たぶんこの最後の式だけキャストしても通るんじゃないですかね。

Comments

[miagolare]

最後に掛け算をするというのをすっかり忘れていました。
丁寧にご回答いただきありがとうございます！