Atcoder 競プロ典型90問 「016 - Minimum Coins」における拡張ユークリッドの互除法による解法の一部が分からない

Question

質問内容

Atcoder 競プロ典型90問 「016 - Minimum Coins」の問題（https://atcoder.jp/contests/typical90/tasks/typical90_p ）を解説3（https://atcoder.jp/contests/typical90/editorial/1148 ）に載っている拡張ユークリッドの互除法による方法で実現しようとしましたが，ソースコード（変更前）ではACを出すことができませんでした．同コンテストから参照できるソースコード（https://github.com/hoso629/kyopro_educational_90/blob/main/016.cpp ）
を参考にし一部加筆したソースコード（変更後）を投稿することでACは出せましたが，この修正でなぜ問題が解決できるようになるかが分かりません．ご教授お願い致します．

ソースコード(変更前)

import sys
sys.setrecursionlimit(10**7)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 10000

    # a[1]とa[2]の最大公約数d
    d = gcd(a[1],a[2]) 

    # a[1]*y+a[2]*z=dにおけるy,zの一般解pq[0],pq[1]
    pq = [0,0]
    exd_gcd(a[1],a[2],pq) 

    # 後の計算のためにa[1]とa[2]を互いに素な値にする
    a[1] = int(a[1]/d) 
    a[2] = int(a[2]/d)

    # 一番安い硬貨の枚数xを固定する
    for x in range(0,10000):
        # 一番安い硬貨だけでn円を越した場合
        if (n-a[0]*x) < 0:
            break     
        # a[1]*y+a[2]*z= n-a[0]*x の整数解が存在する場合
        if (n-a[0]*x) % d == 0:

            # 一般解からa[1]*y+a[2]*z= n-a[0]*xにおける整数解の1つ(y,z)を求める
            y,z = int(pq[0]*(n-a[0]*x)/d), int(pq[1]*(n-a[0]*x)/d)
            if y >= 0:
                # yが0以上の条件を満たす状況においてy+zの最小値を求める
                t= int(y/a[2]) 
                y -= t*a[2]
                z += t*a[1]
            else:
                # yが0以上の条件を満たす状況においてy+zの最小値を求める
                t= int((-y+a[2]-1)/a[2])  
                y += t*a[2]
                z -= t*a[1]    

            # zが整数解にならなかった場合
            if z < 0:
                continue

            # コインの総和の最小値を更新
            ans = min(ans, x+y+z)

    print(int(ans))

# ユークリッドの互除法
def gcd(a,b):
    if a < b:
        a,b = b,a
    if b == 0:
        return a 
    else:
        return gcd(b, a % b)

# 拡張ユークリッドの互除法（a*pq[0]+b*pq[1]=gcd(a,b)を満たすpq[0],pq[1]の整数解を求める）
def exd_gcd(a,b,pq):
    if b == 0:
        pq[0]=1
        pq[1]=0
        return a
    d = exd_gcd(b, a % b, pq)
    pq[0],pq[1] = pq[1],pq[0]-int(a/b)*pq[1]
    return d

main()

ソースコード(変更後)

import sys
sys.setrecursionlimit(10**7)

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.sort()
    ans = 10000

    # 変更点：aの中の順番を変えることで後のループで枚数を固定するコインを
    # 最も価値が高いものに変更する
    a[0],a[2] = a[2], a[0]
    a[1],a[2] = a[2], a[1]

    # (以下同文のため省略)

補足情報

言語：Python (PyPy 3.11-v7.3.20)
不正解のテストケースの内容は非公開

Answer 1

原因は、割り算(小数点以下切り捨て)をint(a/b)で計算していることです。

Pythonで割り算(小数点以下切り捨て)をint(a/b)と書いた場合、a/bの部分は浮動小数点数で計算され、その後int()で整数に変換されます。その際、a/bの部分で浮動小数点数の誤差が入り込み、正しい結果にならない場合があります。

Pythonで割り算(小数点以下切り捨て)をしたい場合は、a // bと書いてください。

原因から分かる通り、実は変更前後とも正しくない結果を返す場合があります。念のため、変更前後ともうまくいかない入力例を挙げておきます。

760563774
996446692 436843249 760563774

Comments

[catworld]

解決しました．
入力例と共に分かりやすい説明ありがとうございます．