本履歴

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

動的計画法ふたたび

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

nを整数とする。{0,1,2,3}のいずれかを係数とする多項式P(x)であって、
P(2)=nとなるようなものの個数を求めよ。

ぱっと見、DPなのでプログラム書いてみた。

require "memoize"
include Memoize

Coefficients=0..3
M=2
LOGM=Math::log(M)

#dp[n,k]=P(M)=nとなる係数0,1,2,3の多項式で、次数がk次以下のものの個数
#dp[n,k+1]=dp[n,k]+d[n-M**(k+1),k]+...+dp[n-i*M**(k+1),k]..+dp[n-3*M**(k+1),k]
def dp(n,k)
	return 0 if n<0
	return 1 if k==0&&Coefficients===n
	return 0 if k==0
	Coefficients.inject(0){|r,c|r+=dp(n-c*M**k,k-1)}
end
memoize(:dp)

#find the min p s.t. n<M**p
def max_order(n)
	(Math::log(n)/LOGM).ceil
end

1.upto(100){|n|puts"%d:%d"%[n,dp(n,max_order(n))]}

動かしたら、1,2,2,3,3,4,4,5,5,6,6,7,7,...という数列が出てきた。答えは、[n/2]+1。シンプルすぎて逆に不思議だ、答えは分かったが謎はまだ明らかになってない、と思い証明を試みたが結局できなかった。さすが上級編。
解答を見ると、次の方針で解いていた。

  • a_0+2*a_1+4*a_2+...=nとなるa_iの組の個数を求めることに帰着される。
  • f(x)=(1+x+x^2+x^3)(1+x^2+x^4+x^6)(1+x^4+x^8+x^12)...=1/(x-1)(x^2-1)のx^nの係数が求めるもの
  • がんばってテイラー展開してね

(あ、これってポリアの本に載っていた両替問題だ!)

この解法をみると、F(2)=nの2と係数が{0,1,2,3}であることからf(x)がキレイになったのが分かった。
(もう一つより一般の別解が載っていた、F(m)=n,係数{0,1,2,...,m^2-1}の答えが[n/m]+1)

さて、閉じた式、素晴らしい。O(1)だ。俺のプログラム、O(nlogn)だ。
でも、係数を{0,1,2,3}でなく{0,1,2,3,4}にすると紙上では途端に通用しなくなるよ。fが汚くなる。
数学の問題と競技プログラムの問題は、こういったところが違う気がするな。

最後に、Coefficients=0..4にして動かしたプログラムは、逆に考えると、簡単にならなかった複雑なf(x)をテイラー展開してるんだよね、数学的解法を知らなければ気づけなかったこと、これもへぇーだな。