AtCoder ARC #058 : E - 和風いろはちゃん / Iroha and Haiku

F解くのに手こずってた。
http://arc058.contest.atcoder.jp/tasks/arc058_c

問題

長さN、各要素1～10のいずれかをとる数列A[0]…A[N-1]を考える。
整数X,Y,Zに対し

• sum(A[x...(y-1)])=X
• sum(A[y...(z-1)])=Y
• sum(A[z...(w-1)])=Z

を満たす0≦x＜y＜z＜w≦Nが存在するようなAはいくつあるか。

解法

自分はわりとゴリ押し。
Aの末尾の要素いくつかを覚えておいて、先頭から1～10を当てはめたとき末尾の要素が条件を満たすX,Y,Zを成すかどうかを覚えながら処理するDPで解いていった。
末尾の要素は全部覚える必要はなく、最大でもX+Y+Z要素なのでメモリや時間が足りないことはない。

int N,X[4];

map<vector<int>,int> MP;
vector<vector<int>> V;

vector<int> E[22];

int state[50050][12];
ll dp[50][20202];
ll mo=1000000007;

int isok(vector<int> v) {
	int cur=0, st=0, ng=0;
	FORR(r,v) {
		cur+=r;
		if(cur==X[st]) st++,cur=0;
		else if(cur>X[st]) return 0;
	}
	return 1+(st==3);
}

int getstate(vector<int> v) {
	
	int ret=isok(v);
	
	if(ret>0) {
		if(ret==2) return 0;
		MP[v]=MP.size();
		V.push_back(v);
		E[v.size()].push_back(MP[v]);
		return MP[v];
	}
	while(1) {
		v.erase(v.begin());
		if(isok(v)==2) return 0;
		if(MP.count(v)) return MP[v];
	}
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>X[0]>>X[1]>>X[2];
	
	V.push_back(vector<int>());
	V.push_back(vector<int>());
	
	MP[vector<int>()]=1;
	E[0].push_back(1);
	FOR(i,18) {
		FORR(r,E[i]) {
			vector<int> v=V[r];
			for(x=1;x<=10;x++) {
				v.push_back(x);
				state[r][x]=getstate(v);
				v.pop_back();
			}
		}
	}
	
	dp[0][1]=1;
	FOR(i,N) FOR(j,V.size()) for(x=1;x<=10;x++) (dp[i+1][state[j][x]] += dp[i][j])%=mo;
	ll ret=0;
	FOR(j,V.size()) ret += dp[N][j];
	cout<<dp[N][0]<<endl;
	
}

まとめ

Editorialはもう少しスマートな解き方をしているね。