SRM 501 500pt: FoxAverageSequence

TopCoder

keyword

動的計画法　C++

問題概要

長さN(<40)、値がM(=40)以下の数列がある。ただし、値のいくつかは不定である。不定な部分に[0,M]の値を入れて美しい配列にしたい。何通りあるかをmodで求める問題。美しい配列とは次の2条件を満たす。

  • どの連続する3つも狭義単調減少でない。
  • a[i]の値はa[0],...,a[i-1]の相加平均以下である。

解法

dp[今何番めを調べているか][それまでの和][その配列の値][単調減少が何回続いたか]でO(N*M^4)。メモリもギリギリ足りるけど、これに関しては配列を再利用すれば全く問題なく解決できる。2倍程度の高速化をしたら無事通った。ちなみに、特定の入力にだけ反応するような定数倍最適化は最悪ケースでのテストがやりにくくなるだけなのでやらない方がいいと思う。逆に、どの入力に対しても同程度に効く最適化ならそれは意味のあることだと思う(もちろん計算量が際どいという前提で)。例えばa%=MOD;をif(a>MOD) a-=MOD;に置き換えるとか。

感想

ローカルだと2番目以降のテストケースでglobal配列が初期化されないのを忘れていた。最近の500にしては取り組みやすい問題だったと思う(もっとも、より計算量の小さい解法があるそうだが)。

int dp[41][41][1601][3];
const int mod = 1000000007;

class FoxAverageSequence {
public:

int theCount(vector <int> seq) {
	//for(int i=0; i<41; i++)for(int j=0; j<41; j++)for(int k=0; k<1600; k++)for(int l=0; l<3; l++) dp[i][j][k][l] = 0;
	int N = seq.size();
	int maxV = 0;
	if(seq[0] == -1){
		for(int i=0; i<=40; i++){
			dp[0][i][i][0] = 1;
		}
		maxV = 40;
	}
	else{
		dp[0][seq[0]][seq[0]][0] = 1;
		maxV = seq[0];
	}
	for(int i=0; i<N-1; i++){
		if(seq[i+1] != -1){
			for(int j=0; j<=40; j++){
				for(int k=maxV; k>=0; k--){
					if(k < seq[i+1]*(i+1)) break;
					for(int l=0; l<2; l++){
						dp[i+1][seq[i+1]][k+seq[i+1]][seq[i+1]<j?l+1:0] =
								((int64)dp[i+1][seq[i+1]][k+seq[i+1]][seq[i+1]<j?l+1:0] + dp[i][j][k][l])%mod;
					}
				}
			}
			maxV += seq[i+1];
		}
		else {
			for(int k=maxV; k>=0; k--){
				for(int a=0; a<=40; a++){
					if(k < a*(i+1)) break;
					for(int j=0; j<=40; j++){
						for(int l=0; l<2; l++){
							dp[i+1][a][k+a][a<j?l+1:0] =
									((int64)dp[i+1][a][k+a][a<j?l+1:0] + dp[i][j][k][l])%mod;
						}
					}
				}
			}
			maxV += 40;
		}
	}

	int64 ret = 0;
	for(int i=0; i<=40; i++){
		for(int j=0; j<=1600; j++){
			for(int l=0; l<2; l++){
				ret += dp[N-1][i][j][l];
				ret %= mod;
			}
		}
	}

	return (int)ret;
}