2010 ICPC国内予選 C.ポロック予想

問題概要

n番目の正四面体数はn(n+1)(n+2)/6で表される。
10^6未満の整数Nが与えられたとき、Nを正四面体数の和で表すのに必要な、最小の正四面体数の個数を求めよ。
また、Nを「奇数の正四面体数」で表すのに必要な、最小の「奇数の正四面体数」の個数を求めよ。

解法

動的計画法による。

以下の解法はかなり遅いもの。
まず10^6未満の全ての正四面体数をを列挙する。
そして、dp[i]にiを作るのに必要な正四面体数の個数を入れて更新していく。

全ての正整数は5つ以下の正四面体数の和で表すことができる、と問題文にあるので
ループを5回回せばよいのだが、5つ以下の奇数の正四面体数の和で全ての正整数が表せるかどうかは書いてない。が、10^6未満の数に対してはどうも5回のループで十分なようだった。

ソースコード

const int MX=1000000;

int tet[1000],ntet;
int dp[MX],dpOdd[MX];

int main(){
	
	ntet=0;
	for(;;ntet++)
	{
		tet[ntet]=ntet*(ntet+1)*(ntet+2)/6;
		if(tet[ntet]>=MX)break;
	}
	
	rep(i,MX)dp[i]=dpOdd[i]=inf;
	dp[0]=dpOdd[0]=0;
	int mx=0;
	rep(i,5)rep(j,mx+1)
	{
		rep(k,ntet)
		{
			if(j+tet[k]>=MX)break;
			if(tet[k]%2==1)dpOdd[j+tet[k]]=min(dpOdd[j+tet[k]],dpOdd[j]+1);
			dp[j+tet[k]]=min(dp[j+tet[k]],dp[j]+1);
			mx=max(mx,j+tet[k]);
			mx=min(mx,MX-1);
		}
	}
	
	int n;
	while(cin>>n,n)cout<<dp[n]<<" "<<dpOdd[n]<<endl;
	
	return 0;
}