この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

アルゴリズムと計算量の問題

難易度 4大学院入試の標準レベル大学数学アルゴリズムと計算量

$1$ 円、 $7$ 円、 $10$ 円の硬貨がそれぞれ十分な枚数あるとする。正の整数 $n$ に対し、 $n$ 円をちょうど支払う硬貨の組み合わせのうち枚数が最小のものの枚数を $O (n)$ とする。また、次の貪欲法で $n$ 円を支払ったときの枚数を $G (n)$ とする。

貪欲法：残りの金額が $0$ になるまで、残りの金額以下で額面が最大の硬貨を $1$ 枚使う。

$1 ≦ n ≦ 100$ を満たす整数 $n$ のうち、 $G (n) > O (n)$ となるものの個数を求めよ。

この問題で使うもの

貪欲法が最適でない場合の判定（説明と入口の問題）
動的計画法の基本（硬貨の最小枚数）（説明と入口の問題）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$n = 10 q + r$ と分けて、 $G (n)$ を $q$ と $r$ で表し、 $r$ ごとに貪欲法より少ない枚数で払えるかを調べる。

ヒント 2

$7$ 円 $2$ 枚は $14$ 円で、 $10$ 円 $1$ 枚と $1$ 円 $4$ 枚（合計 $5$ 枚）を $2$ 枚で置きかえられる。最適性の確認には「 $7$ 円と $10$ 円を $k$ 枚、うち $7$ 円が $s$ 枚なら金額は $10 k - 3 s$ 」を使う。

ヒント 3

$q ≧ 1$ かつ $r = 4, 5, 6$ なら、 $10$ 円を $1$ 枚減らして $7$ 円 $2$ 枚を使うと $3$ 枚少なくなる。それ以外の $r$ では、枚数の下界と $3 s$ の値の整数性から貪欲法が最小になることを確かめる。

答えと解説

答えを見る

27

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

$n = 10 q + r$ （ $q ≧ 0$ , $0 ≦ r ≦ 9$ は整数）と書く。貪欲法はまず $10$ 円を $q$ 枚使い、残り $r$ 円を $r ≧ 7$ なら $7$ 円 $1$ 枚と $1$ 円 $r - 7$ 枚で、 $r < 7$ なら $1$ 円 $r$ 枚で払う。よって
$G (n) = q + g (r), (g (0), \dots, g (9)) = (0, 1, 2, 3, 4, 5, 6, 1, 2, 3) .$

最小枚数の下界. 硬貨は $1$ 枚あたり高々 $10$ 円なので、枚数は $⌈ n /10 ⌉$ 以上である。また $7$ 円と $10$ 円だけを $k$ 枚使い、そのうち $7$ 円が $s$ 枚なら金額は $10 k - 3 s$ である。

$r \in {4, 5, 6}$ かつ $q ≧ 1$ の場合. $10$ 円を $q - 1$ 枚、 $7$ 円を $2$ 枚、 $1$ 円を $r - 4$ 枚使うと $10 (q - 1) + 14 + (r - 4) = 10 q + r = n$ で、枚数は $q + r - 3$ 。 $G (n) = q + r$ より小さいので $G (n) > O (n)$ 。

$q = 0$ の場合（ $1 ≦ n ≦ 9$ ）. $10$ 円は使えない。 $n ≦ 6$ なら $1$ 円だけで $n$ 枚しかなく貪欲法と一致し、 $n = 7, 8, 9$ なら $7$ 円を $1$ 枚使うのが最小で、これも貪欲法と一致する。

残りの $r$ （ $q ≧ 1$ ）で貪欲法が最適であること.
- $r = 0$ ： $G = q = n /10$ で下界と一致。
- $r = 1, 7$ ： $G = q + 1 = ⌈ n /10 ⌉$ で下界と一致。
- $r = 2$ ： $G = q + 2$ 。 $q + 1$ 枚で払えるとすると、 $q + 1$ 枚の合計は $10 (q + 1)$ 以下で、 $1$ 円を $1$ 枚でも含むと合計は $10 q + 1$ 以下になるので、すべて $7$ 円か $10$ 円。 $10 (q + 1) - 3 s = 10 q + 2$ より $3 s = 8$ となり不可能。よって $O = q + 2$ 。
- $r = 8$ ： $G = q + 2$ 。同様に $q + 1$ 枚なら $3 s = 2$ で不可能。 $O = q + 2$ 。
- $r = 3$ ： $G = q + 3$ 。 $q + 1$ 枚なら $3 s = 7$ で不可能。 $q + 2$ 枚なら、 $1$ 円を $2$ 枚以上含むと合計は $10 q + 2$ 以下で不足するので、 $1$ 円は $0$ 枚か $1$ 枚。 $0$ 枚なら $10 (q + 2) - 3 s = 10 q + 3$ より $3 s = 17$ 、 $1$ 枚なら $10 (q + 1) - 3 s + 1 = 10 q + 3$ より $3 s = 8$ で、どちらも不可能。 $O = q + 3$ 。
- $r = 9$ ： $G = q + 3$ 。 $q + 1$ 枚なら $3 s = 1$ で不可能。 $q + 2$ 枚なら $1$ 円は $0$ 枚か $1$ 枚で、 $3 s = 11$ または $3 s = 2$ となり不可能。 $O = q + 3$ 。

以上より、 $G (n) > O (n)$ となるのは $q ≧ 1$ かつ $r \in {4, 5, 6}$ のときに限る。 $1 ≦ n ≦ 100$ では $q = 1, 2, \dots, 9$ の各 $q$ について $3$ 個ずつ（ $14, 15, 16, 24, 25, 26, \dots, 94, 95, 96$ ）あり、 $n = 100$ は $r = 0$ で該当しない。よって求める個数は
$9 \times 3 = 27.$

別解

$n = 10 q + r$ （ $0 ≦ r ≦ 9$ ）とおく。

貪欲法: $q$ 枚の $10$ 円のあと、余り $r$ を $7$ 円と $1$ 円で支払う。 $r = 0, \dots, 9$ に対する枚数は $g (r) = 0, 1, 2, 3, 4, 5, 6, 1, 2, 3$ 。よって $G (n) = q + g (r)$ 。

最適解: $O (n) = 1 + min (O (n - 1), O (n - 7), O (n - 10))$ 、 $O (0) = 0$ を順に計算すると
$O (1..9) = 1, 2, 3, 4, 5, 6, 1, 2, 3$ 、 $O (10..19) = 1, 2, 3, 4, 2, 3, 4, 2, 3, 4$ 、 $O (20..29) = 2, 3, 4, 5, 3, 4, 5, 3, 4, 5$ 、……となり、 $n ≧ 10$ では $O (n) = q + h (r)$ 、 $h (r) = 0, 1, 2, 3, 1, 2, 3, 1, 2, 3$ （ $r = 0, \dots, 9$ ）であることが確かめられる（例: $r = 4$ は $14 = 7 + 7$ を使い $q - 1$ 枚の $10$ 円と合わせて $q + 1$ 枚、 $r = 5$ は $35 = 7 \times 5$ を使い $q + 2$ 枚、 $r = 6$ は $56 = 7 \times 8$ を使い $q + 3$ 枚）。

$n ≦ 9$ では $10$ 円が使えないので $G (n) = O (n)$ 。

$n ≧ 10$ では $G (n) - O (n) = g (r) - h (r)$ で、 $r = 4, 5, 6$ のとき $3$ 、それ以外は $0$ 。したがって $G (n) > O (n)$ となるのは $n ≧ 10$ かつ $r \in {4, 5, 6}$ のとき。

$1 ≦ n ≦ 100$ では $q = 1, \dots, 9$ の各 $q$ で $r = 4, 5, 6$ の $3$ 個ずつ、すなわち $14, 15, 16, 24, 25, 26, \dots, 94, 95, 96$ の $27$ 個（ $n = 100$ は $r = 0$ で等しい）。

検算: $n = 24$ は貪欲法で $10 + 10 + 1 \times 4$ の $6$ 枚、最適は $10 + 7 + 7$ の $3$ 枚で $G > O$ 。 $n = 17$ は $10 + 7$ で両方 $2$ 枚。

答え: $27$

アルゴリズムと計算量の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題