今回のコンテストはいかがでしたでしょうか。難しい問題も多かったと思いますが、楽しんでいただけたのであれば幸いです。

初心者の方へ

• プログラミングを始めたばかりで何から手を付ければよいか分からない方は、まずは practice contest の問題 A「Welcome to AtCoder」をお試しください。
• また、プログラミングのコンテストに慣れていない方は AtCoder Beginners Selection の問題をいくつか試すことをおすすめします。

---

1 円玉と 10 円玉だけの場合

この問題では硬貨が 6 種類もあり考えると複雑になってしまうので、まずは \(1\) 円玉と \(10\) 円玉に限定した以下の問題を考えましょう。

問題 AtCoder さんは \(1\) 円玉 \(A\) 枚と \(10\) 円玉 \(C\) 枚を持っている。これから \(N\) 個の店でそれぞれ \(X_1, \dots, X_N\) 円の買い物をその順に行う。すべての店で「ちょうどの金額」を支払って商品を購入することが可能か判定せよ。

1. 具体例を考える

例として、\(1\) 円玉 \(14\) 枚と \(10\) 円玉 \(3\) 枚を持っていて、\(X_1 = 22\) 円と \(X_2 = 13\) 円の買い物をする場合を考えます。最初は \(22\) 円の買い物をします。

今できるひとつの支払い方は「\(10\) 円玉 \(2\) 枚と \(1\) 円玉 \(2\) 枚」です。

今できるもうひとつの支払い方は「\(10\) 円玉 \(1\) 枚と \(1\) 円玉 \(12\) 枚」です。

次は、\(13\) 円の買い物をすることになります。前者のケースであれば、\(10\) 円玉 \(1\) 枚と \(1\) 円玉 \(3\) 枚でちょうど支払えます。しかし、後者のケースであれば、ちょうど支払うことはできません。

なぜ前者のケースでは成功したのに後者のケースでは失敗したのでしょうか？

2. 10 円玉を使えるときに使おう

後者のケースで \(13\) 円ちょうどを支払えなかった理由は、\(1\) 円玉が少なくとも \(3\) 枚必要なところで、\(2\) 枚しか残っていなかったからです。最初の買い物で \(1\) 円玉 \(12\) 枚を消費したから、足りなくなってしまいました。逆に、前者のケースでは \(1\) 円玉を大切に残したから成功しました。

\(10\) 円玉が余っているのにわざわざ \(1\) 円玉を追加で \(10\) 枚使って買い物をするメリットは全くありません。なぜなら、残しておいた \(10\) 円玉を未来の買い物で使ったとしても結局は、今の買い物でその \(10\) 円玉を使って、その未来の買い物で \(1\) 円玉 \(10\) 枚を使うのと同じだからです。

よって、\(10\) 円玉をできるだけ使って \(1\) 円玉をたくさん残しておく戦略が最適です。この戦略でシミュレーションを行い、すべての店で支払うことができたら答えは Yes、できなかったら答えは No、と判定することができます。

---

問題の解説

\(1, 5, 10, 50, 100, 500\) 円玉がある場合でも同じ考え方ができます。各買い物で、高い硬貨を残してその分を安い硬貨で支払うメリットは全くありません。

厳密な説明（上級者向け）

証明したいこと: $(p_1, p_2, \dots, p_6) = (1, 5, 10, 50, 100, 500)$ とする。ある買い物 X をする時点で「目的達成のためには絶対に『$p_i$ 円玉が残った状態で $p_1, \dots, p_{i-1}$ 円玉を $p_i$ 円以上支払わなければならない』」という状況にはなり得ないこと。

買い物 X で使った $p_1, \dots, p_{i-1}$ 円玉の枚数を $a_1, \dots, a_{i-1}$ 枚とします $(a_1 p_1 + \dots + a_{i-1} p_{i-1} \geq p_i)$。まず、これらの硬貨からいくつかを選んでちょうど $p_i$ 円を作れることを証明します。$a_k p_k \dots + a_{i-1} p_{i-1} \geq p_i$ となる最大の $k$ を考えます。$s = a_{k+1} p_{k+1} \dots + a_{i-1} p_{i-1}$ とします。このとき、$p_k$ 円玉を $\frac{p_i-s}{p_k}$ 枚、$p_{k+1}, \dots, p_{i-1}$ 円玉をそれぞれ $a_{k+1}, \dots, a_{i-1}$ 枚使えばちょうど $p_k$ 円にになります。ここで、$\frac{p_i-s}{p_k}$ は必ず整数になります。理由は、$s$ と $p_i$ が両方とも $p_k$ の倍数だからです。

前述の硬貨の選び方を $S$ として、証明したいこと は以下のように証明できます。

• この後の買い物で一切 $p_i$ 円玉を使わない場合: 買い物 X で、$S$ の硬貨の代わりに $p_i$ 円玉を使えます。
• この後の買い物で一切 $p_i$ 円玉を使う場合: 買い物 X で $S$ の硬貨の代わりに $p_i$ 円玉を使い、この後の買い物で $p_i$ 円玉の代わりに $S$ を使う、と変えることができます。

よって、各買い物における最適な戦略は以下のようになります。

• 残り金額が \(499\) 円以下になるか手元の \(500\) 円玉がなくなるまで、\(500\) 円玉でできるだけ支払う
• （中略）
• 残り金額が \(4\) 円以下になるか手元の \(5\) 円玉がなくなるまで、\(5\) 円玉でできるだけ支払う
• 残り金額を \(1\) 円玉で支払う

この戦略でシミュレーションを行い、すべての店で支払うことができたら答えは Yes、できなかったら答えは No、と判定することができます。

---

実装例

C++ での実装例は https://atcoder.jp/contests/arc177/submissions/53283608 です。

Python では以下のように実装できます。

# 入力
a, b, c, d, e, f = map(int, input().split())
n = int(input())
x = list(map(int, input().split()))

# シミュレーション
ans = True
for v in x:
	while v >= 500 and f >= 1:
		v -= 500
		f -= 1
	while v >= 100 and e >= 1:
		v -= 100
		e -= 1
	while v >= 50 and d >= 1:
		v -= 50
		d -= 1
	while v >= 10 and c >= 1:
		v -= 10
		c -= 1
	while v >= 5 and b >= 1:
		v -= 5
		b -= 1
	while v >= 1 and a >= 1:
		v -= 1
		a -= 1
	if v != 0:
		ans = False
		break

# 出力
print('Yes' if ans == True else 'No')