読者です 読者をやめる 読者になる 読者になる

KOJ 0017

programming

これを解いてみた。
コーディングはしてませんが。

問題概要

500円の商品をa+b個売るのだがおつりを全く用意していない。
客はひとつずつ商品を買っていく。
a人は千円札しか持っていないが、b人は500円玉を持っている。
売る順番を工夫すればうまくやりくりできるが、売る順番は何通りあるか?
ただし、客の区別はつけない。

解法

DPすれば解けそうだが、数学っぽく解くことにする。


千円札しか持っていない人をA、500円玉を持っている人をBと呼ぶ。
つまり、Aはa人、Bはb人いる。
a = 4, b = 6のときの問題を下図に対応させる。
f:id:snuke:20111225193913p:image
赤線をまたがないように、左下から右or上に辺を辿っていって右上に辿り着く方法の数が答えになる。
上に辿ることがAに商品を売ること、右に辿ることがBに商品を売ること、に対応している。


さて、このままだと数式に出来ないので、少し言い換えをする。
「赤線をまたがないように辿る場合の数」は
「普通に辿る場合の数」ー「赤線をまたいで辿る場合の数」
となる。
「赤線をまたいで辿る場合の数」というのはつまり、
f:id:snuke:20111225193914p:image
上図の「オレンジの●を通って辿る場合の数」ということ。
それは、
f:id:snuke:20111225193912p:image
上図のように赤線で折り返すと簡単に求まることが分かる。


まあつまり、計算式としては、

a+b C a - (a-1)+(b+1) C (a-1)
= a+b C a - a+b C a-1

となります!(Cはコンビネーションね)
以上〜