【AtCoder】ABC085C - Otoshidama の解説 in Python

はじめに

AtCoder Beginners Selection の Otoshidama という問題を解きました。
一重ループでいい感じに解けたので解説してみようと思います。👀

提出結果

実行時間	メモリ	コード長
10ms	8724 KB	292 Byte

Otoshidama の問題文は以下をご参照ください。

🚀 方針

$10,000$円札、$5,000$円札、$1,000$円札の枚数をそれぞれ、$x$、$y$、$z$ 枚として三元一次方程式を解きます。入力として、合計金額 $Y$ 円（yen）とお札の合計枚数 $N$ 枚（nbills）が与えられるため、つぎの2本の方程式が立ちます。

\begin{cases}
10000x + 5000y + 1000z = Y \\
x + y + z = N
\end{cases}

あと1本の方程式は $x$ の値を仮定することで対応します。
本問は、解の組み合わせを1つ見つける、または解がないことを示せば良いので、この方針でいきます。

🧠 回答

python

nbills, yen = map(int, input().split())
xyz = '-1 -1 -1'
for x in range(yen//10000+1):  # xは正の整数である
    yf = (yen/1000-nbills-9*x)/4  # yについての方程式
    if yf >= 0 and yf.is_integer():  # 正の整数であることを保証する
        y = int(yf)
        z = nbills -x -y  # zが定まる
        if z >= 0:  # 正である（整数であることは保証済み）
            xyz = f'{x} {y} {z}'
            break
print(xyz)

ポイントは、「yについての方程式」です。forループによって $x$ が決まると、$y$ の値は (yen/1000-nbills-9*x)/4 に定まります。この方程式はつぎのようにして導かれます。

$y$ を $x$ で表します。

\begin{cases}
10000x + 5000y + 1000z = Y \\
x + y + z = N
\end{cases}

上式の両辺を1000で割る。

\begin{cases}
10x + 5y + z = Y/1000 \\
x + y + z = N
\end{cases}

上式と下式の差をとって $z$ を削除する。

9x + 4y = Y/1000 - N

$y$ について解く。

y = \frac{Y/1000 - N - 9x}{4}

これで $y$ の値が決まります。

$x$ と $y$ が決まったので、$z$ は $z = N - x - y$ に定まります。

ただし、$x$、$y$、$z$ はお札の枚数なので、正の整数（0を含む）である必要があります。

ここで、x は、range(<整数>) をイテレートした値であるため、正の整数であることが保証されます。

y は、 / を用いた演算により float 型になるので、if文を用いて正の整数であることを保証します（ちなみに、y が少数となる可能性を示唆するため、 y に値する変数名を yf としています）。

z は整数同士の減算なので、整数であることが保証されます。あとは、if文の制御で、z が正であることを保証します。

さいごに

お読みいただきありがとうございました！
質問等ございましたらお気軽にコメントください 😄