ABC169-Cについて

AtCoder Beginner Contest 169のC問題 "Multiplication 3" について、納得できない箇所があったので検証してみる。

注意

当記事ではこの問題の解答も記している。まだ解いていない方は気を付けてほしい。

この問題について

この問題は整数Aと小数Bを受け取り、AxBの小数点以下を切り捨てた整数値を出力する問題である。ここで0<=A<=10¹⁵, 0<=B<=10で、Bは小数第2位まで与えられる。

問題のリンクはこちら -> https://atcoder.jp/contests/abc169/tasks/abc169_c

納得できない部分

A * (int)(B * 100) / 100･･･(1) を出力するとWAとなり、
A * (Bの整数部分 * 100 + Bの小数部分) / 100･･･(2) を出力するとACとなる点。

例えば、以下のようにBの整数部分、小数部分を分けて受け取り、(2)を計算して出力するとACとなる。

int main() {
    int64_t a, b_sei, b_syou; // 左からA, Bの整数部分, Bの小数部分
    scanf("%lld %lld.%lld", &a, &b_sei, &b_syou);

    cout << a * (b_sei*100 + b_syou) / 100 << endl;
}

しかし、以下のようにBを小数としてそのまま受け取り、(1)を計算して出力するとWAとなる。

int main() {
    int64_t a;
    double b;
    cin >> a >> b;
 
    cout << a * (int)(b*100) / 100 << endl;
}

検証

(1)と(2)のどちらも正しい結果を出力するように見える。しかし実際は、(1)の方法を用いるといくつかのケースでWAとなってしまう。
そのため、様々なA, Bを与え、(1)(2)で結果が異なるようなケースを探してみようと思う。

検証結果

検証用プログラム(記事末尾に記載)を作成して実行したところ、そのようなケースがどんどん出てきた(出ても数個かなと思っていたので驚いた)。
キリがないのでA = 10までのケースを記載する。1行が1ケースを表し、A, Bの順に記載されている。

5, 4.60
5, 8.20
5, 9.20
7, 0.29
7, 0.58
7, 1.15
7, 8.29
7, 9.29
8, 1.13
9, 4.56
9, 4.89
9, 8.12
9, 8.45
9, 8.78
9, 9.12
9, 9.45
9, 9.78
10, 2.30
10, 4.10
10, 4.60
10, 5.10
10, 8.20
10, 8.70
10, 9.20
10, 9.70
(以下略)

このうち、一番上のケース(A, B) = (5, 4.60)を例にとり、(1)(2)の方法で計算させてみる。すると(2)では問題なく23と出力されたが、(1)では22と誤った結果が出力されてしまった。

結局(1)の何が問題なのか

再度(1)の式を掲載する。
A * (int)(B * 100) / 100･･･(1)
このうち、Bの100倍を求める部分で誤差が出てしまっていると思われる。

実際に試してみる。
B=4.60として、B*100を(1)(2)の方法で求めてみる。
すると、(1)のように(int)(B*100)とした場合には459という誤った結果が出力されていることがわかった(おそらくintにキャストする部分で誤差が出ているのではないかと思う)。

Appendix. 検証用プログラム

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

int main() {
    int64_t b_seisuu, b_syousuu;
    double b;
    
    for (int64_t a = 0; a <= (int64_t)pow(10, 15); ++a) {
        for (int i = 0; i <= 1000; ++i) {
            // 入力データBの用意
            ostringstream sout;
            sout << setfill('0') << setw(3) << i;
            string b_str = sout.str();
            b_str.insert(b_str.end()-2, '.');

            // (1) ACとなる方法
            sscanf(b_str.c_str(), "%ld.%ld", &b_seisuu, &b_syousuu);
            int64_t ans1 = a * (b_seisuu*100 + b_syousuu) / 100;
            
            // (2) WAとなる方法
            sscanf(b_str.c_str(), "%lf", &b);
            int64_t ans2 = a * (b*100) / 100;

            // 比較
            if (ans1 != ans2) {
                cout << a << ", " << b_str << endl;
                //cout << ans1 << ", " << ans2 << endl;
                //return 0;
            }
        }
    }
}

日記

日本語の勉強のためのブログ