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

本履歴

購入した古本の履歴と時々プログラミング

動的計画法を使ってみた

プログラムコンテストをやり始めて一番納得いかないは動的計画法。Dynamic Programming(DP)
まず分かんないのは、その名前。全く意味不明。計画ってw 中途半端になんか関係ありそうなのが更に悪い。
名付け親の人には、焼き土下座だな、ぷんすかぷん。
さて、今もって良く分からない気持ち悪い状態なのだが、この前自分のプログラムで幸運にも使えたので以下覚え書き。

先日買った組合せ論の精選102問 (数学オリンピックへの道)に次のような問題があった。

4 x 4のマス目に1、-1を書き入れて、どの行の和も、どの列の和も0であるようにする方法は何通りか?

これを暇つぶしに解いてみた。次の同値な問題を考える:

4 x 4のマス目に黒石を置いて、どの行も、どの列も黒石がちょうど2個であるようにする置き方は何通りか?

まず、紙で解いてみた。黒石を上2行のそれぞれの行に2個置くことを考える。どんな置き方をしても必ず置くことはできる。
このとき、列方向でみてみると配置のパターンは次の三通り:

   
   

というように2個黒石の列が2つあるパターン(P1)。6通り。

   
   

一つの列だけ2個黒石のパターン(P2)。4*3*2=24通り。

   
   

2個黒石の列がないパターン(P3)。6通り

それぞれのパターンで、3、4行目の黒石の置き方を確認しよう。
P1の場合は、3、4行目は1通りしかない。
P2の場合は、2通り。
P3の場合は、6通り。
従って、6*1+24*2+6*6=90通り。大正解!
答えはあっていたのだが、6 x 6で同じことを考えてみる。紙だと難しいな、面倒なのでプログラムを書いてみた。

MAX=6
MAX2=MAX/2

#population of 1
def pop(n)
	r=0
	while n>0
		r+=n%2
		n/=2
	end
	r
end

def valid(nums)
	MAX.times.all?{|i|nums.map{|a|a[i]}.inject(:+)==MAX2}
end

three_pop_nums=((1<<MAX)-1).times.map.reject{|n|pop(n)!=MAX2}

count=0
three_pop_nums.repeated_permutation(MAX).each{|nums|
	count+=1 if valid(nums)
}
p count

各行を二進表示された整数と考える。黒石があるところが1が立っている箇所。
three_pop_numsが二進表示したときに1が3つ立っている整数。
そこから重複順列(6乗!)で6つ縦に並べたときに、各列に1は3つあるか?あればプラス1というコード。
まあ、6x6は通っても10x10は通りませんな。


んで、色々考えた結果、次のようなコードができた。多分DP。

require "memoize"
include Memoize

MAX=12
MAX2=MAX/2

#numsはsortされていると仮定
def dp(nums)
	return 0 if nums.first<0
	return 1 if nums.inject(:+)==0
	sum=0
	[*0..MAX-1].combination(MAX2){|indices|
		_nums=nums.dup
		indices.each{|idx|_nums[idx]-=1}
		sum+=dp(_nums.sort)
	}
	sum
end
memoize(:dp)

p dp([MAX2]*MAX)

dp[]というMAX次元配列を考えよう。
一番上の行から黒石をMAX2個ずつ置いていくのだが、途中で手を止めて各列の黒石の数をカウントする。x,y,z,u,v,wだったとする。
dp[x,y,z,u,v,w]を各列の黒石の数がx,y,z,u,v,wとなる黒石の置き方の(途中までの)総数とすると、求めるのはdp[MAX2,...,MAX2]。
対称性があるのでdp[x,y,z,u,v,w]=dp[s(x,y,z,u,v,w)] where s:置換
dp[0]=1
dp=dp[x-1,y-1,z-1,u,v,w]+dp[x-1,y-1,z,u-1,v,w]+...+dp[x,y,z-1,u,v-1,w-1]+dp[x,y,z,u-1,v-1,w-1]
であることを利用し、途中の結果はmemoizeでメモ化して、結局MAX=12までは求められた。めでたし。
dpを小さい数字から計算していけば、もっと速いのだろうなあ、再帰より。
関係ないが、オンライン整数列大辞典で検索したら、即ヒット。すごいw
http://oeis.org/A058527

DPとはDPという名の配列に計算結果をメモする方法、でいいや。