AtCoderABC176のB問題がWAになってしまう

Question

前提・実現したいこと

AtCoderの、ABC176のB問題についてです。
何個かのテストデータが通らず、WAになってしまいます。

###B問題
整数 Nが9の倍数であることと、Nを十進法で表したときの各桁の数の和が9
の倍数であることは同値です。
Nが9の倍数であるか判定してください。

######制約

• 0<=N<10^200000
• Nは整数

#####入力
標準出力から、Nが与えられる。

#####出力
Nが9の倍数ならば'Yes'、そうでないなら'No'を出力せよ。

該当のソースコード

C++を用いてプログラムを作成しています。 num は、入力の N です。

1、Nの格桁の和が9の倍数であることを用いました。

#include <stdio.h>
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

int main(){
  long long num, sum=0;

  cin >> num;

  while(num!=0){
  	sum += num%10;
  	//cout << "sum =" << sum<<endl;
  	num = num/10;
  	//cout << "num = " << num << endl;
  }

  if(sum%9 == 0){
  	cout << "Yes" << endl;
  }
  else{
  	cout << "No" << endl;
  }
}

2、Nが9の倍数かどうかそのまま調べました。

#include <stdio.h>
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>

using namespace std;

int main(){
  long long num;

  cin >> num;

  if(num%9 == 0){
  	cout << "Yes" << endl;
  }
  else{
  	cout << "No" << endl;
  }
}

試したこと

2つのプログラムどちらも問題の入力例にある、

• 123456789 -> Yes
• 0 -> Yes
• 31415926535897932384626433832795028841971693993751058209749445923078164062862089986280 -> No

はうまくいきます。自分でも思いつくテストは試してみたのですが、うまくいっているように思えます。
通らないテストデータの例が思いつかないので、ご教授いただけると嬉しいです。
よろしくお願い致します。

Comments

[_Victorique__]

制約間違ってません？

Answer 1

long long　の範囲より大きい数字が入ると
num = 9223372036854775807　になって全てNoになりますね
9999999999999999999999999999999999 →No

自分でテストケースを作る場合、
極端にデカい/小さい
明らかに合ってる/間違ってる
問題に出てきた境界の前後の数字　辺りを組み合わせて試してみるといいです

あと、受け取ったデータが正しく受け取れているか、をすぐ確認するように、
この場合だと
cin >> num;
の下に
cout << "num = " << num << endl;
を書く癖を付けとくとやりやすいです

Comments

[beimax]

ありがとうございます！これからそうする癖をつけます！

Answer 2

データ型の範囲 | Microsoft Docs

long long ではオーバーフローしていませんか？
文字列から1文字ずつ取り出して、数値にして加算していけばいい気がします。

Visual C++ だとエラーで教えてくれました。

エラー: C2177: 定数が大きすぎます。

型が表せる値の範囲は numeric_limits で確認できます。

numeric_limits - cpprefjp C++日本語リファレンス

#include <iostream>
#include <limits>

int main()
{
    std::cout << "long long" << std::endl;
    std::cout << "min " << std::numeric_limits<long long>::min() << std::endl;
    std::cout << "max " << std::numeric_limits<long long>::max() << std::endl;

    //long long
    //min -9223372036854775808
    //max 9223372036854775807
}

サンプルコード

以下で AC しました。

#include <iostream>
#include <string>

using namespace std;

int main()
{
    std::string input;
    cin >> input;

    // 文字列を1文字ずつ読み込んで、int に変換して加算する。
    int sum = 0;
    for (auto c : input)
        sum += c - '0';  // char -> int

    if (sum % 9 == 0)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

Comments

[beimax]

コードまで付けていただいてありがとうございます！理解できました。
桁数に気をつけなくてはいけないのですね。

この問題の模範解答を見ると、C言語では
char s[200010];
とchar型の配列を作って数値を受け取っていたのですが、char型では何桁の数値まで受け取れるのでしょうか？200010という配列の大きさがどこから導かれたものなのかわかりませんでした...

[tiitoi]

オーバーフローを気にする必要があるのは入力を数値 (int や long long など) として変数に入れる場合です。
今回の場合、入力を文字列として変数に入れるので、オーバーフローは気にする必要がありません。
入力の最大値が 10^200000 という条件で、最大200000文字の数値列が入力されるということなので、余裕を持って200010文字分の配列を確保したのでしょう。

char s[200010]; に格納できるのは、ヌル文字を除いて 200009 文字まで格納できます。

C++ を使うのであれば、out of range のバグを避けるために、
文字列であれば、char * 配列ではなく、std::string
配列であれば、 c の配列 (例 int arr[1000] ) でなく、std::vector を使いましょう。

[beimax]

ご回答ありがとうございます！本当に助かりました。