天下一プログラマーの続き

programming

前回の続き。
天下一プログラマーコンテストの予選第一回の3問目が効率の良い方法で解けなかったので調べてみた。というか、他の人が公開しているコードを探しただけ。で、参考にさせてもらったのはここ http://romanchu.blog105.fc2.com/blog-entry-402.html。その結果が下のコード（ほぼ丸写し）。何となく DP で解けそうな気がしたんだけど、そこから先が思いつかなかった。

money = [1, 5, 10, 50, 100, 500, 1000, 2000, 5000, 10000]
man   = 10000 + 1
count = Array.new(man, 0)
count[0] = 1

money.length.times { |i|
    man.times { |j|
        k = j + money[i]
        break if k >= man
        count[k] += count[j]
    }
}

puts count.last

10000 円は大変なので、10 円までで何通りあるかを求める方法を追っていってみる。その場合に count がどのように変化していくかを表示させる。

[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # 初期状態
[1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0] # i:[0], j:[0], k:[1]
[1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0] # i:[0], j:[1], k:[2]
[1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0] # i:[0], j:[2], k:[3]
[1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0] # i:[0], j:[3], k:[4]
[1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0] # i:[0], j:[4], k:[5]
[1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0] # i:[0], j:[5], k:[6]
[1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0] # i:[0], j:[6], k:[7]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0] # i:[0], j:[7], k:[8]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0] # i:[0], j:[8], k:[9]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] # i:[0], j:[9], k:[10]
[1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1] # i:[1], j:[0], k:[5]
[1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 1] # i:[1], j:[1], k:[6]
[1, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1] # i:[1], j:[2], k:[7]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1] # i:[1], j:[3], k:[8]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 1] # i:[1], j:[4], k:[9]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 3] # i:[1], j:[5], k:[10]
[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 4] # i:[2], j:[0], k:[10]
  • count[k] は k 円は何通りの作成方法があるかを記録する変数。k = 0 は 1 とする。
  • i = 0 のとき、1 円のみを使っての k 円の作成方法の数を求める。1 円しか使わないので全て1通り。
  • i = 1 のとき、5 円 + j 円で k 円の作成方法の数を求める (5 円は固定なので、j 円の作成方法の数で k 円の作成方法の数が決まる)。k が 5 未満の場合は 5 円を使うことができないので処理の対象外。k が 5以上10未満の場合の例を k = 5 で書くと、5(money[i])円 + 0(j)円 = 5(k)円 になる。i = 0 のときに求めた 1 円のみでの 5 円の作成方法の数に 0 円の作成方法の数を足す。count[5] += count[0]。k = 10 の場合、5(money[i])円 + 5(j)円 = 10(k)円 となる。なので、作成方法の数は count[10] += count[5]で求められる。count[5]は先の計算で求めた。
  • i = 2 のとき、10 円 + j 円 で k 円の作成方法の数を求める。k が 9 未満の場合は 10 円を使うことができないので処理の対象外。k が 10 の場合、10(money[i])円 + 0(j)円 = 10(k)円 となり、count[10] += count[0] で求めることができる。
  • i > 2 では、使うお金が 10 円より大きくなり 10 円を作成できないので処理終了。

なんだ、わざわざ日本語にしなくても、コードに要約されてんじゃん。こんなわかりにくい説明よりコードの方がわかりやすいぞ。って、はじめからコードを見て動作の原理がわかれば、わざわざ日本語に置き換えて理解しようとしなくてもいいんだけど、それがなかなかできないんだよね。こうやってとりあえず置き換えてみることで理解していくしかないのですょ、私は。
この説明、後から見たらきっと、何言ってるのかわからないだろうな〜。