Problem 0537 : Bingo

問題概要

日本語なので本文参照。
（http://rose.u-aizu.ac.jp/onlinejudge/ProblemInfo.jsp?id=0537）

あまりにわからなくて鬱った。

解法

単純なDPだとTLE.

int n,m,s,dp[2][2001][3001];

int main()
{
	while(scanf("%d%d%d",&n,&m,&s),n){
		rep(i,m+1)rep(j,s+1)dp[0][i][j]=0;
		dp[0][0][s]=1;
		m=min(m,s);
		
		int cur=0,next=1;
		rep(i,n*n){
			rep(j,m+1)rep(k,s+1)dp[next][j][k]=0;
			for(int j=i;j<=m;j++)
			for(int k=j*(n*n-i);k<=s;k++)if(dp[j][k])
			{
				for(int l=j+1;l<=m;l++){
					if(k<l)break;
					dp[next][l][k-l]=(dp[next][l][k-l]+dp[cur][j][k])%mod;
					if(l*(n*n-i)>k)break;
				}
			}
			swap(cur,next);
		}
		int ans=0; rep(i,m+1)ans+=dp[cur][i][0];
		printf("%d\n",ans);
}

次が、dp[j][k]を求めるのに、一個前の値を再利用してオーダーを落とした方法（情報オリンピックの解説）

一個前の値を再利用ができるかは、DPの配列を表で書いて、依存関係を矢印で表したときに、だーっと集中してる矢印があるかを見てやるイメージな気がしてきた。

int n,m,s;
int dp[2][2001][3001];

int main()
{
	while(scanf("%d%d%d",&n,&m,&s),n){
		rep(j,m+1)rep(k,s+1)dp[0][j][k]=0;
		dp[0][0][0]=1;
		m=min(m,s);
		int cur=0,next=1;
		for(int i=1;i<=n*n;i++){
			rep(j,2)rep(k,s+1)dp[next][i-1+j][k]=0;
			for(int j=i-1;j<m;j++)for(int k=n*n-i+1;k<=s;k++){
				dp[next][j+1][k]=dp[cur][j][k-(n*n-i+1)]+dp[next][j][k-(n*n-i+1)];
				if(dp[next][j+1][k]>100000)dp[next][j+1][k]-=100000;
			}
			swap(cur,next);
		}
		int ans=0; rep(i,m+1)ans+=dp[cur][i][s];
		printf("%d\n",ans%100000);
	}
	return 0;
}

ちなみにmodをとる部分を%演算子を使うとTLEになる。
が、これでもMLEになってしまうので、テーブルの更新順序を工夫することで、テーブルを使いまわしてメモリを節約する。

3次元の表は2次元のテーブルのセルがさらに細かく部屋に分かれてるイメージでやると更新の関係とか掴みやすいかなあ。
あーうーほんっとDPが全然できないorzorzorzorzorz

ソースコード

int n,m,s;
int dp[50][3001];

int main()
{
	while(scanf("%d%d%d",&n,&m,&s),n){
		rep(i,n*n+1)rep(j,s+1)dp[i][j]=0;
		dp[0][0]=1;
		m=min(m,s);
		
		rep(i,m){
			for(int j=n*n;j>0;j--)for(int k=s;k>n*n-j;k--){
				dp[j][k]=dp[j-1][k-(n*n-j+1)]+dp[j][k-(n*n-j+1)];
				if(dp[j][k]>100000)dp[j][k]-=100000;
			}
		}
		printf("%d\n",dp[n*n][s]);
	}
	return 0;
}