Make Purse Light 解説

問題名：Make Purse Light
出典：Problem B, ACM/ICPC Practice Contest for Japan Domestic, 2005-06-19
難易度：☆
問題の種類：探索
解法：特になし
解答ソースコード：
- p0006-deq_1.cpp （全探索）
- p0006-deq_2.cpp （解析的な解法）

この問題には解法が2種類あります。一つは全ての組み合わせに対して全探索する方法です。もう一つは，問題をよく読めば解を簡単に求められることが分かり，それは問題依存の解析的な解法だといえます。

解法1：全探索

アルゴリズムの概略

持っている10円玉，50円玉，100円玉，500円玉の全ての組み合わせに対して，店員にお金を渡してお釣りを計算します。その計算結果により，つまり「現在の枚数 = 最初持っていた枚数 - 支払った枚数 + お釣りの枚数」が求まるので，その最小値を与える支払い硬貨の組み合わせが解になります。

アルゴリズムの計算量

ループはそれぞれの硬貨の最大枚数 c に対して回って4重ループになるので，計算量は O(c⁴) になります。ループの内側は評価が難しいですが，計算量のオーダーとしては定数と考えられるので O(1) です。従って，O(c⁴ × 1) で O(c⁴) が全体の計算量になります。ただし，一回のループでの計算量はそこそこかかります。

ここでは c=20 なので，20⁴ = 160,000 回です。この数字は問題あるのかないのかよく分かりません。ループの内側の計算がもし100クロックかかるとすると，全体の計算量は 16,000,000 クロック = 16Mクロックです。 1GHzのCPUでは一つの問題に対して0.05秒くらいで終わりそうです。しかし，一つの問題セットにテストケースは最大100個くらいは含まれていそうです。全てのケースが最悪の計算量 (20⁴) を求められるケースではないでしょうが，もし100つ全てが最悪であれば「16Mクロック×100 = 1.6Gクロック」，1GHzのCPUでは数秒かかりそうですね。もしかしたらループの内側の計算が 1000クロックかかって数十秒はかかるかもしれませんが，数分や数十分かかることはなさそうです。

ここで，この問題が国内予選での出題なのか，アジア地区予選やPKUなどでの出題なのかで，このアルゴリズムを選択するかどうかが変わってきます。というのも，例年国内予選ではプログラムの実行を各参加者のPC上を行い，出力結果のみをサーバに送る仕様になっているので，数十秒程度かかっても正解であればOKなのです。しかし，アジア地区予選やPKUではプログラムのソースコードをサーバに送り，実行はサーバ上で行われるので，実行時間に制限時間が設けられていてそれを越えるとTLE (Time Limit Exceeded) となって不正解だとみなされます。 TLEは長くてもたいてい数秒程度になっているので，この計算時間ではプログラムが通らない可能性があります。

通常，想定された正しいアルゴリズムを使えばTLEの10分の1～100分の1程度の計算時間で済みます（ぎりぎりに設定されていることはありません）。ですから，このアルゴリズムは想定解ではなさそうなのですが，国内予選ではTLEがないので他に解法が思い浮かばなければこの解法を用いることになります。

アルゴリズムの実装

お釣りの枚数の計算ですが，例えば釣銭が 300 円だとすると，10円玉や50円玉は返されずに100円玉が返されます。言い換えれば，釣銭が100円以上であれば10円玉や50円玉よりも100円で返された方が枚数が少なくなります。ですから，最初に500円玉で返せるかをチェックし，次に100円玉，50円玉，最後に10円玉とチェックしていくと釣銭の硬貨を正しく計算できます。擬似コードでかくと，

ct[4] = [10, 50, 100, 500]  // coin type（硬貨の種類）

for i in [3, 2, 1, 0]:
  while sum >= ct[i]:
    sum -= ct[i];
    rc[i]++;  // returned coin（釣銭の各硬貨の枚数）

という感じになります。

アルゴリズムの評価

実際にこのプログラムを与えられた入力に対して実行すると，だいたい5～8秒程度かかるようです（コンパイラの最適化オプションを最高に設定すると3秒くらいで終わりました）。前述の計算量の推定値とだいたい合致していますね。計算時間的にギリギリという感がありますが，国内予選では問題ない時間です（なお，アジア地区予選やPKUでも数秒かかるからダメというわけでもなく，解くのに数秒かかる問題も出たりします）。

解法2：解析的な解法

アルゴリズムの概略

上記では全ての硬貨の組み合わせに対して全探索を行いましたが，実はそんなことをしなくても解が求まる方法があります。その方法はとても単純で，「持っている全ての硬貨を店員に渡す」というアイデアです。そうすると店員から最適な枚数が返ってきますが，それは支払うべき金額を払った状況において最小の枚数になっているはずです。ですから，それが求めたかった解なのです。

ただし，10円玉を3枚渡して10円玉が2枚返ってくる，というような渡し方は正解ではありません。同じ硬貨が返ってくる場合は最初から渡さないようにしなければなりません（と問題に書かれております）。ですから，各種類の硬貨について，「最初持っていた枚数 - 戻ってきた枚数」が払うべき枚数になります。

アルゴリズムの計算量

このアルゴリズムは全探索の場合のループの内側と同じ計算量になり，それはだいたい定数時間なので計算量のオーダーは O(1) になります。これは全く問題となりません。

アルゴリズムの実装

注意点は全探索の場合と同様です。

$Id: index.shtml 1335 2007-03-01 09:06:39Z SYSTEM $

deq notes