http://www.gsic.titech.ac.jp/supercon/supercon2007/youkou.html
高校生のプログラミングコンテスト、予選問題は
- ある金額をなるべく少ないコインで出す方法を計算せよ。67円=50+10+5+1+1 とか。
- おつりも考えて、92円のとき102円出すような解を出すようにせよ
- コインの額面が1,5,10,50 ... でない一般の場合でも計算せよ
アメリカではクオーターをとっさに何枚出せばいいか、慣れませんでしたねそういえば。32セントとかだと 25+5+1+1が最適。
まだ予選中なんで詳しくはかけないけど、コインの額面が常識的な「ある条件」を満たす場合とそうでない場合で探索の方法が変わってくると思う。自分なら常識的な場合に特化して書くかな。ナップサック問題とかだとこの条件が成り立つと自明な問題になっちゃう。
というわけでコードを書くのはいいけど、blog に載せるのはまずいかも。
じゃあ
実際に例えばCITIBANKとかからこういう仕様書が来て納入するとする。世界のどこかには非常識なコインの体系があるかもしれない。それをどうするか。一般的な場合まで含めてコーディングするのはワークロードやバグや処理速度の点から効率的でない。常識的な場合のみ作り、非常識な場合は非常識なコインを存在しないものとして扱えばいい。コインの額面を各国の納入先で入力し、それが常識的でない場合に警告を出して無視するコインを選んでもらう。
追記
この問題をNP困難問題として解いている日記を発見。二週間前に書かれている。出題者の意図は「NP困難問題を高校生に解かせてやれイッヒッヒ」ということのようだ。高校生諸君、がんばってくれ。
7/3追記
まずは1, 2, 4, 8, 16 ... 円コインの場合を考えるとよさげだな。出す方法は一意。おつりは、たとえば0xf7円とか0x33円とかの場合を考えてみる。
