Difficulty 24の問題でコケてしまった悲しみ。
AtCoder Beginner Contest 165のB問題、問題名「1%」は、高橋くんが100円持っていて、銀行に預けると年利1%(複利)の利子がつくのですが、ある金額X円に達するには何年かかるか答えよ、という問題です。
自分で作った回答コードはこちら。
<?php
fscanf(STDIN, "%d", $X);
// 預金額
$money = 100;
// 利子（％）
$risoku = 1;
// 答え
$ans = 0;
while($X > $money) {
$money += intval($money * ($risoku / 100));
$ans++;
}
printf("%d", $ans);
結果、不正解となったコードですが、どこが間違っているか分かりますでしょうか？
利子を変数にして1%じゃなくても答えが出せるんだぜ的にしてしまったのが悪かった。
正解になったのはこちら。
<?php
fscanf(STDIN, "%d", $X);
// 預金額
$money = 100;
// 答え
$ans = 0;
while($X > $money) {
$money += intdiv($money, 100);
$ans++;
}
printf("%d", $ans);
変数とか使った私が愚かでした。単純に100で割って端数を切り捨てた整数を返してくれる intdiv を素直に使いました。
ちなみに、不正解となったテストケースは「99-after-contest-01.txt」という名前で、値Xは 974755271730884810 です。
具体的にいくらかというと、 97京4755兆2717億3088万4810円 ということなので、 ビル・ゲイツも真っ青なお金なので1年の誤差なんか気にすんな という気分になりますが、不正解は不正解。
テストケース名から分かる通り、コンテスト後に作られたテストケースなので、コンテスト時はいわゆる 嘘解法(テストケース的にはOKだけどコードとしては実際には間違っている、の意） で通した人も少なからずいるんでしょうね。
不正解のコードと正解のコードでは、3432年後から値に差が出始めます。（■がついているところは同値）
左が不正解のコードで、3431年後の金額、…66199円の1%は…661円なので、3432年後は …66199+…661=…860となるべきところ、…861となっています。
この影響で、差がどんどん広がり、不正解のコードでは 974755271730884810 に達するのは3757年後と算出するのに対し、正解のコードでは3758年後となるので、不正解となるのです。
いやぁ、不正解のコード、そんなに悪いコードですかねぇ🤒、という気分になってしまいますが、いまだに浮動小数点を含む演算には気をつけなければいけないケースがあるんだなぁ、ということは留意しておいた方が良いんですね、というお話でした。