LoginSignup
aobu04
@aobu04

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

ABC345-CでWAとなってしまう理由を教えてください…

Q&AClosed

解決したいこと

ABC345-Cで、以下のコードで提出すると1つのテストケースでWAとなる理由につきまして、どなたか教えていただきたいです。よろしくお願いいたします。
https://atcoder.jp/contests/abc345/tasks/abc345_c

該当するソースコード

C++


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

int main() {
    string S;
    cin >> S;
    int charCount[30] = {0};

    for (char c : S) {
        charCount[c - 'a']++;
    }
    
    ll mns = 0;
    bool on = true;
    
    for (int i = 0; i < 26; ++i) {
        if (charCount[i] > 1) {
            mns+=charCount[i]*(charCount[i]-1)/2 ;
            on = false;
        }
    }
    
    if(on == false){
      cout << S.size() * (S.size()-1) /2 - mns +1 << endl;
      return 0;
    } else {
      cout << S.size() * (S.size()-1) /2  << endl;
      return 0;
    }
    
}




0

2Answer

問題見て気になったのが 文字列長さ $10^{6}$ 個入力した場合どうなりますか?

bが1個 と aが999999.....の場合とか
baaaaaaaaaaaa....................aaaaa

1

Comments

  1. @aobu04

    Questioner

    確かに長い文字列でのエラーみたいですね、ありがとうございます。

原因はオーバーフローです。

以下のコードで、どのように計算が行われるか考えてみてください。

            mns+=charCount[i]*(charCount[i]-1)/2 ;

charCount[i]の型がintなので、上記の計算はmnsへの加算の直前までintで行われます。

また、文字列の長さの最大が$10^6$なので、charCount[i]も最大$10^6$となり、上記計算で最悪$10^{12}$弱の値が現れる可能性があります。

intの最大値は$2,147,483,647$なので、$10^{12}$弱の値はオーバーフローしてしまい、正しい計算が行われません。

1

Comments

  1. @aobu04

    Questioner

    丁寧に回答してくださりありがとうございます。charCountがint型であることに気づいていませんでした…

  2. 納得できたのであれば、本問をクローズしましょう。

Your answer might help someone💌