Google Code Jam 2010 Round 3

GCJ

B

N種類の大きさの板を使って、長さLになるように積み上げたい。どの板も好きなだけ使って良いが、全部で使う枚数を最小にしたいので、その最小枚数を答えよ、という問題。


Lが十分大きいので、最終的には一番大きいのをできるだけ多く使うことになる。これは、一番大きいのの大きさをBとして、それよりも小さいbというものを使うことを考えると、bをB枚使うよりもBをb枚使う方が枚数の面で得をするためである。


従って、大きさB以外の板を使ってL%Bになるように積み上げることを考える。このとき、何枚の板を既に使っていて、達成した大きさがいくつであるか、というのを状態に持つようにしたい。実際にはこれだと状態数が多過ぎるので、法Bについて考える。L/Bがいくつかを覚えておけば、以降で必要になるBの枚数が減ることになる。つまり、今までに使った枚数から引いて考えて良い。(これはLが十分に大きいため。)


以上を整理すると、状態として、今までに何枚使ったか、達成した大きさは法Bでいくつか、何枚Bを使わないで済むようにできたか、というものを持っておいて、L%Bに到達するまでの最短距離を求めたい。最短距離については、ダイクストラをやれば良いので、実装を頑張ればおしまい。