【AtCoder】ABC159 D - Banned K で嵌った話 【C++】

0. 前提

• ３月２２日（日）のAGC159が競プロ初参戦。
• １番慣れている言語はPythonだったが、いい機会なのでC++を勉強することにした。
• C++はAtCoderのHP上にある
  C++入門 AtCoder Programming Guide for beginners (APG4b)をひと通りやってみた。
• 他に最適化処理などアルゴリズム関連の知識不足を痛感したので蟻本を購入し初級編を半分程度終わらせたところでAtCoderデビューした。

1. ABC159 D - Banned K

• 問題

* 結果 最初の５問でハマりました。いろいろ試してみたものの原因がわからないままここで制限時間の100分が終了しました。苦い競プロデビューとなりました。。。。

2. ハマった点

• わかってしまえば非常に単純な点なのですが、オーバーフローが原因でした。提出したコードはだいたい以下のような感じ。

# include <bits/stdc++.h>
using namespace std;
 
int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> count(N, 0);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
        count.at(A.at(i)-1)++;
    }
 
    int sum = 0;
    for (int i = 0; i < N; i++) {
        int c = count.at(i);
        sum += c*(c-1)/2;
    }
 
    for (int i = 0; i < N; i++) {
        cout << sum - max(count.at(A.at(i)-1)-1, 0) << endl;
    }
} 

• 以下の行がオーバーフローしていました。

        sum += c*(c-1)/2;

• $A_i$の最大値は200,000ですが、int型は-2,147,483,648〜+2,147,483,647の範囲しか取れないので、c*(c-1)の計算をするところでオーバーフローを起こし得ます。
• ということで以下のようにコードを修正しました。

# include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main(){
    int N;
    cin >> N;
    vector<int> A(N);
    vector<int> count(N+1, 0);
    for (int i = 0; i < N; i++) {
        cin >> A.at(i);
        count.at(A.at(i))++;
    }

    ll sum = 0;
    for (int i = 0; i < N + 1; i++) {
        ll c = count.at(i);
        sum += c*(c-1)/2;
    }

    for (int i = 0; i < N; i++) {
        cout << sum - (count.at(A.at(i))-1) << endl;
    }
}

• 通った！！

• long long型はint型の倍の8byteを使用しますが、-9,223,372,036,854,775,808〜+9,223,372,036,854,775,807の範囲を扱えます。
• 誰もが１回は通る落とし穴なのかもしれませんが、僕も無事落とし穴を経験しながら成長していく、と笑