なんとな~くしあわせ?の日記

JavaとかAWSの設定とかをメモする技術ブログ

ゼロから始める動的計画法 - コイン問題

問題設定

Project Euler Problem 31

ターゲットとする問題は以下

イギリスでは硬貨はポンド£とペンスpがあり,一般的に流通している硬貨は以下の8種類である. 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
以下の方法で£2を作ることが可能である.
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
これらの硬貨を使って£2を作る方法は何通りあるか?

考察

文系大学生の気持ちでいろいろ考えてみる

  • 枚数をちょっと考えてみる
    • 200ポンドを1ペンス硬貨で作る⇛1ペンス×200枚で達成、最も枚数が多そう
    • 200ポンドを1ポンド硬貨で作る⇛1ポンド×1枚で達成、最も枚数が少なそう
    • 場合の数の合計がパない
  • せや!総当たりや
    • 硬貨の価値が最も高いものから順にループを組み、合計値が200になったものを記録する
    • さて、コインの種別は何個やったかな?、1, 2, 5, 10, 20, 50, 100, 200やから8種類やな!
    • 8 重 ル ー プ
    • 処理重すぎて止まるコンソール

しかしこれでは競技プログラミングには勝てません、どうしましょう

動的計画法による解答

ここからは、もっと計算量の少ない方法を、YouTubeの動画から解説を引用して流れを追っていきたいと思います。計算量の少ない方法とは 動的計画法 - Wikipedia です。

www.youtube.com

問題を簡単にする

まず、合計金額が N = 5 となるように、コイン { 1, 2, 3 } を使って支払いの方法を数え上げるとしよう。普通に数え上げると、以下のように5通りになるはず。

  • {1, 1, 1, 1, 1}
  • {1, 1, 1, 2}
  • {1, 1, 3}
  • {2, 3}
  • {2, 2, 1}
なぜ動的計画法か?
  • 問題が入れ子構造になっているので、動的計画法を使うことができる
    • 例えば、コインの1枚めに1を使うとすれば、残りN=5-1=4 の問題に化ける
    • N=4の問題を予め解いておけば、数え上げが楽になるというわけだ
まずは2次元配列で

(1) コインの種別を行、合計値を列に取る集計表を考える

  • 表の行は支払いに使えるコインの種別に関係しており、行の一番上からその行までのコインのみを使って支払いを行う
  • コインの種別は、 C1 = 1, C2 = 2, C3 = 3 という記号で表すことにする

C\N 0 1 2 3 4 5
C1=1
C2=2
C3=3

(2) N = 0, の場合支払い方はすべて1通りしかない(0枚支払うということ、なんじゃそら)。ここまでは準備。

C\N 0 1 2 3 4 5
C1=1 1
C2=2 1
C3=3 1

(3) C1 のみ使える場合, 支払い方はすべて1通りしかない。合計金額がいくつであっても、1円で支払う方法は各自1通りしかない。

C\N 0 1 2 3 4 5
C1=1 1 1 1 1 1 1
C2=2 1
C3=3 1

(4) C1とC2が使える状態を考える, ここからが重要。それぞれ①〜⑤で印をつけた

  • ここからは、対象の行の硬貨を1枚使うか使わないかをシミュレートする。

C\N 0 1 2 3 4 5
C1=1 1 1 1 1 1 1
C2=2 1
C3=3 1

(4)-① : N = 1

  • C2を 1枚使う方法 ⇛ 合計金額を超えてしまうので0通り
  • C2を 0枚使う方法 ⇛ C1を使ってN=1を目指す方法なので、これは先程求めている1通り
  • 合計1通り

(4)-② : N = 2

  • C2を 1枚使う方法 ⇛ 1枚使えば合計金額ピッタリ、よって1通り
  • C2を 0枚使う方法 ⇛ C1だけを使ってN=2を目指す方法なので、これは先程求めている1通り
  • 合計2通り

(4)-③ : N = 3

  • C2を 1枚使う方法 ⇛ 1枚使うと N=3-2=1、これはC1だけでN=1を目指す問題に化ける、よって1通り
  • C2を 0枚使う方法 ⇛ C1だけを使ってN=3を目指す方法なので、これは先程求めている1通り
  • 合計2通り

(4)-④ : N = 4

  • C2を 1枚使う方法 ⇛ 1枚使うと N=4-2=2、これはC1,C2を使ってN=2を目指す問題に化ける、よって2通り
  • C2を 0枚使う方法 ⇛ C1だけを使ってN=4を目指す方法なので、これは先程求めている1通り
  • 合計3通り

(4)-⑤ : N = 5

  • C2を 1枚使う方法 ⇛ 1枚使うと N=5-2=3、これはC1,C2を使ってN=3を目指す問題に化ける、よって2通り
  • C2を 0枚使う方法 ⇛ C1だけを使ってN=5を目指す方法なので、これは先程求めている1通り
  • 合計3通り

というわけで表が埋まる

C\N 0 1 2 3 4 5
C1=1 1 1 1 1 1 1
C2=2 1 1 2 2 3 3
C3=3 1

(5) C1,C2,C3が使える状態を考える。それぞれ①〜⑤で印をつけた

  • 同様にして、対象の行の硬貨を1枚使うか使わないかをシミュレートする。

C\N 0 1 2 3 4 5
C1=1 1 1 1 1 1 1
C2=2 1 1 2 2 3 3
C3=3 1

(5)-① : N = 1

  • C3を 1枚使う方法 ⇛ 合計金額を超えてしまうので0通り
  • C3を 0枚使う方法 ⇛ C1,C2を使ってN=1を目指す方法なので、これは先程求めている1通り
  • 合計1通り

(5)-② : N = 2

  • C3を 1枚使う方法 ⇛ 合計金額を超えてしまうので0通り
  • C3を 0枚使う方法 ⇛ C1,C2だけを使ってN=2を目指す方法なので、これは先程求めている2通り
  • 合計2通り

(5)-③ : N = 3

  • C3を 1枚使う方法 ⇛ 1枚使えば合計金額ピッタリ、よって1通り
  • C3を 0枚使う方法 ⇛ C1,C2だけを使ってN=3を目指す方法なので、これは先程求めている2通り
  • 合計3通り

(5)-④ : N = 4

  • C3を 1枚使う方法 ⇛ 1枚使うと N=4-3=1、これはC1,C2を使ってN=1を目指す問題に化ける、よって1通り
  • C3を 0枚使う方法 ⇛ C1,C2だけを使ってN=4を目指す方法なので、これは先程求めている3通り
  • 合計4通り

(5)-⑤ : N = 5

  • C3を 1枚使う方法 ⇛ 1枚使うと N=5-3=2、これはC1,C2を使ってN=2を目指す問題に化ける、よって2通り
  • C3を 0枚使う方法 ⇛ C1,C2だけを使ってN=5を目指す方法なので、これは先程求めている3通り
  • 合計5通り

というわけで表が埋まる

C\N 0 1 2 3 4 5
C1=1 1 1 1 1 1 1
C2=2 1 1 2 2 3 3
C3=3 1 1 2 3 4 5

たまたまC3の行は階段状に数値が増加した。組み合わせの総数は配列の最大値となる。よって5通り。

Rubyのコードに落とし込む

  • 表の行と列を舐めて全て見ていくのはfor文の2重ループで実現できる
  • 処理としては、以下の2つに注目してもらいたい
  • coins[i]を1枚使う方法
    • dp[i][j - coins[i]] ← ここまで短縮されるとまるで意味不明。
    • 要は、ある目指すべき合計値N(=j)からループ内で処理しているコインの金額を引いて、その時の計算済みの場合の数を見に行っている
    • わからなければ、上に戻って手順の文章を読むと良いです
  • coins[i]を0枚使う方法
    • dp[i-1][j]
    • ここは、ループ内で処理しているコインを使わずにある目指すべき合計値N(=j)を達成することのできる、計算済みの場合の数を見に行っている
COINS = [1, 2, 3]

def coin(amount,kind,coins)

  coins = [0].concat(coins)
  dp = Array.new(kind+1).map{Array.new(amount+1, 0)}

  dp.each{|row| row[0] = 1}

  for i in 1..kind
    for j in 1..amount
      # coins[i]を1枚使う方法
      first = dp[i][j - coins[i]]
      # coins[i]を0枚使う方法
      second = dp[i-1][j]

      puts "N = #{j}"
      puts "#{coins[i]} を1枚使う方法 => #{first}"
      puts "#{coins[i]} を0枚使う方法 => #{second}"
      dp[i][j] = first + second
    end
  end
  dp
end

N,M = 5,COINS.length
dp = coin(N,M,COINS)

puts dp.max.max

プロジェクトオイラー用に微調整

COINS = [1, 2, 5, 10, 20, 50, 100, 200]

def coin(amount,kind,coins)

  coins = [0].concat(coins)
  dp = Array.new(kind+1).map{Array.new(amount+1, 0)}
  dp.each{|row| row[0] = 1}

  for i in 1..kind
    for j in 1..amount
      dp[i][j] = dp[i][j - coins[i]] + dp[i-1][j]
    end
  end
  dp
end

N,M = 200,COINS.length
dp = coin(N,M,COINS)
p dp.max.max

競プロ始めた - アドカレ用

競プロ始めた

この記事は Competitive Programming Advent Calendar 2017 - Adventar のために書かれました。

adventar.org

あまり新規性のある内容は書けないので、半年ぐらい素人が競プロやってみてどうだったかをつらつら書いてみようと思います。他の人の参考になれば幸いです。

競技プログラミング(AtCoder限定)を始めたのは2017/06/18からです。勝手がわからなかったのか、無謀にもAtCoder Grand Contestに参加しています。当然なにも解けていません。

競プロやろうと思った動機

  • 転職に役立ちそうなので実は前からやろうとは思ってた
  • 働き始めてからこのかた何か作りたいものがいろいろあったけど最近は特になくなってきたため
  • グラフ (データ構造) - Wikipedia の話を見て、現状にも適用できそうだと思ったため *1

AtCoderの感触

最初3ヶ月ぐらいの体感

  • 問題文を読んでも頭に入らない(NとかKってなんぞ?高橋くんって誰)
  • アルゴリズムを学んでないのでとても効率の悪いプログラムを書いてしまう
    • 最初は遅い言語で書いてるのが原因かと思ったのですが、遅い原因の90%は正しいアルゴリズムが選択できていないことのようです
  • AC*2されたコードを読んでも理解できない、解説読んでも理解できない
最初3ヶ月ぐらいの気づき

後半3ヶ月ぐらいの体感

  • 問題文の内容がすぐに頭に入るようになってきた(要は慣れ)
  • 効率の良いアルゴリズムが何か、計算量のオーダー表記について意味がわかってきたのでどうすると計算が遅くなってしまうかわかってきた
  • 他人の書いたコードの意味が徐々にわかってきた
    • 競プロerが書くコードは確かに汚いが、それを理解できない理由は使われているアルゴリズムの仕様を知らないからである
    • あとC++で書かれるコードにマクロを使いまくるために、後から読む人はそれが何かわからない
後半3ヶ月ぐらいの気づき

  • 勉強するときに、コードを書くよりも解説読んだりアルゴリズム要素を探すほうがよさそうだとわかってくる
  • 出題されるアルゴリズム要素は、それなりに限られているようだということ
    • なんとなく、学ぶべき数学としては組合せ、グラフ、確率、整数ぐらいが範囲かと、大雑把に言うと離散数学
  • プロジェクトオイラーはいいぞ

以上からの来年の目標

  • AOJ本、蟻本を読んで問題解く
  • AtCoder Beginners Contest 4完
  • 緑コーダーからの水色コーダー

*1:実際グラフアルゴリズムと数え上げ、組み合わせ、確率らへんはギョームプログラミングに役立つと思う

*2:Acceptedの略、問題文に対して正しいコードを提出するとこういう表示が出る

アルゴリズムまとまってるサイト

メモ用、他にあれば追記する

大学の授業シラバス


このサイトにあったサイトも転記している


ダイクストラの出身校とかでググってもいいレクチャーノート出てこないのはちょっと不思議