13 少数と誤差 Dif:274 ABC189 B：「AtCoder 凡人が『緑』になるための精選50問詳細解説」サンプル

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/f6e495d5d63b46bde374
次：https://qiita.com/sano192/items/d4aba1192a81cf736eae

【目標】
・少数の計算は誤差が出る可能性があることを覚える
・少数が出てくる計算を避けられる実装をできるようになる

【概要】
B問題にも関わらず、コンテスト中にWA(不正解)を出す人が非常に多かった問題。WA(不正解)の理由は少数の誤差が考慮されていなかったこと。計算の途中で少数が出る問題についてはできる限り整数だけで計算できないか？ということを考えるようにしよう。この問題で少数が出てくる問題をどうやって整数のみの計算に置き換えるか、ということを学ぶ。

【方針】
お酒に含まれるアルコール量はV×(P/100)。
素朴にコードに書くと以下のようになる。

N,X=map(int, input().split())

alcohol=0
for i in range(N):
    V,P=map(int, input().split())
    alcohol+=V*(P/100)
    if X<alcohol:
        print(i+1)
        exit()
print(-1)

サンプルも通るから提出・・・するとWA(間違い)となる。

コンピュータは無限小数をそのまま扱えない。内部ではある程度のところで切り捨てや切り上げを行ってしまうため、誤差が出る可能性がある。

上記のコードでは以下のような入力で誤差が生じ、WA(間違い)となってしまう。
1 7
25 28
1杯目はお酒の量が25ml、アルコール度数が28%でアルコール摂取量が25*(28/100)=7mlとなり、ぎりぎり酔わない。つまり答えは-1となるはずだ。

ところがpythonで25*(28/100)を計算すると7.000000000000001となる。
そうなると1を出力してしまい、WA(間違い)となる。

どうすれば少数がでてこないようにできるか。
度数Pを100で割るのではなく、許容量Xを100倍してしまえば全て整数の計算となり、少数をなくすことができる。
つまり
X<V*(P/100)
の両辺を100倍して
100X<VP
としてしまえば良い。

【実装】
まず入力を受け取る。

N,X=map(int, input().split())

摂取したアルコール摂取量を記録する変数alcoholを用意する。最初は0。

alcohol=0

1番目のお酒から順にアルコールの摂取量を計算して足していく。
摂取量の計算はVPとし、これが100Xを超えたら答えを出力する。
最後まで100*Xを超えなければ-1を出力。

for i in range(N):
    V,P=map(int, input().split())
    alcohol+=V*P
    if 100*X<alcohol:
        print(i+1)
        exit()

print(-1)

【コード全文】

N,X=map(int, input().split())

alcohol=0

for i in range(N):
    V,P=map(int, input().split())
    alcohol+=V*P
    if 100*X<alcohol:
        print(i+1)
        exit()

print(-1)

この記事は拙著「AtCoder　凡人が『緑』になるための精選50問詳細解説」のサンプルです
価格：100円
kindle：https://www.amazon.co.jp/dp/B09C3TPQYV
booth(pdf)：https://sano192.booth.pm/items/3179185

前：https://qiita.com/sano192/items/f6e495d5d63b46bde374
次：https://qiita.com/sano192/items/d4aba1192a81cf736eae