AtCoder ABC159 D問題 Banned K

Question

はじめに

閲覧ありがとうございます。AtCoderさんの過去問(リンク)についての質問です。

コード

↓WAのコード
このmain関数の4行目で定義しているvectorの要素の型をintからll intに、combination関数の引数もll intにしたらACしました。

#include <bits/stdc++.h>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; ++i)
#define ll long long
using namespace std;

ll int combination(int n) {
  return n * (n - 1) / 2;  //nC2の計算
}

int main() {
  int n;
  cin >> n;
  vector<int> inputs(n + 10);  //入力
  vector<int> num(n + 10);  //その数がいくつあるか
  vector<ll int> answers(n + 10);  //差分
  ll int all = 0;  //ボールを減らさなかったときの答え
  
  rep(i, n) {
    int a;
    cin >> a;
    ++num[a];  //数値のカウント
    inputs[i] = a;  //入力を保存
  }
  
  rep(i, n + 1) {
    if(num[i] != 0) {
      answers[i] = combination(num[i]) - combination(num[i] - 1);  //差分の計算
      all += combination(num[i]);  //全体の計算
    }
  }
  
  rep(i, n) {
    cout << all - answers[inputs[i]] << endl;  //全体から差分を引いて出力
  }
  
  return 0;
}

質問内容

各種サイトにて答えがオーバーフローするためlong long型が必要と書いてあったので、コンビネーション計算した値を代入するanswers vectorとallをlong longにしたところ(上記コード)、WAでした。

num vectorに入る値の最大値は、すべての入力が同じ数字だった場合のN<= 200000だと考えたため、こちらの要素をll型で定義しなかったところ、WAとなってしまったのです。

ACは取れたのですが、なぜnum vectorもll型にしなければいけないのかが疑問なので質問させていただきます。

エラー等

公開されているテストケース(リンク)をチェックしましたが、やはりnumの要素がオーバーフローするようなことはないと思うのですが...。

Answer 1

ll int combination(int n) {
return n * (n - 1) / 2; //nC2の計算
}

ここでnがintなのでn * (n - 1)がオーバーフローしかねないので
ll int combination(ll int n) {
にする必要があります。

Comments

[shibahama]

returnはlong long int型だけれど、` n * (n - 1) `の計算結果はnがint型であるが故にint型として扱われてしまい、結果オーバーフローして正しくない値がreturnされてしまう...という解釈でよろしいでしょうか？

[asm]

そういうことですね。
double v = 3/2が1.5ではなく1になるのと同様に演算式の評価は式を構成する要素の型によって決まります。

[shibahama]

納得しました！！
ありがとうございます(*^^*)