AtCoder ARC #117 : E - Zero-Sum Ranges 2

このアイデアは後日のCodeforcesの参考になった。
https://atcoder.jp/contests/arc117/tasks/arc117_e

問題

整数N,Kが与えられる。
以下を満たす整数列Aは何通りか。

• Aは、+1と-1がN回ずつ登場する2N要素の数列である。
• Aの部分列のうち、和が0となるのはK通りである。

解法

SをAのPrefix sumとする。するとこの問題はS[i]=S[j]となるような(i,j)の対がK個あるSを作る問題となる。
S[i]とS[i+1]の差の絶対値は1なので、Sをプロットすると、Editorialにあるようなジグザグの山ができる。
よくあるDPだと、S[0]、S[1]、S[2]…と要素順に処理を行うがここでは上下順、すなわち値の大きな方から見て、同じ値を一気に埋めよう。

f(v,flag,n,k,m) := 大きい方からv個めまでの値を決めたとき、あとn要素を配置する必要があり、あとS[i]=S[j]となるような(i,j)をk個作る必要があって、今Sの最小値を持つ要素間でm個の穴がある。flagはS[i]=0となるiを処理済みかどうかのブール値である。このような条件を満たすSの組み合わせ。

解はf(*,true,0,0,0)の総和である。
DPの遷移では、

• flagをtrueに移す
• いくつか穴を埋める
• 穴の間に山の頂点をいくつかする

ということを行うことができる。これらを総当たりしていこう。

int N,K;

ll from[2][66][909][63];
ll to[2][66][909][63];

ll comb(int P_,int Q_) {
	static const int N_=1020;
	static ll C_[N_][N_];
	
	if(C_[0][0]==0) {
		int i,j;
		FOR(i,N_) C_[i][0]=C_[i][i]=1;
		for(i=1;i<N_;i++) for(j=1;j<i;j++) C_[i][j]=(C_[i-1][j-1]+C_[i-1][j]);
	}
	if(P_<0 || P_>N_ || Q_<0 || Q_>P_) return 0;
	return C_[P_][Q_];
}
ll hcomb(int P_,int Q_) { return (P_==0&&Q_==0)?1:comb(P_+Q_-1,Q_);};


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	
	N=2*N+1;
	ll ret=0;
	int up=1;
	for(i=1;i<=N;i++) {
		if(i*(i-1)/2<=K) from[0][N-i][K-(i*(i-1)/2)][i+1]=1;
	}
	
	while(up) {
		ZERO(to);
		up=0;
		
		for(i=0;i<=N;i++) for(x=0;x<=K;x++) for(y=0;y<=N;y++) if(from[0][i][x][y]||from[1][i][x][y]) {
			up=1;
			if(i==0&&x==0&&y==0) ret+=from[1][i][x][y];
			if(y>=2) to[1][i][x][y-2]+=from[0][i][x][y];
			if(y>0) {
				for(j=y;j<=min(i,2*N);j++) {
					int add=j*(j-1)/2;
					if(add>x) break;
					to[0][i-j][x-add][j-y+2]+=from[0][i][x][y]*hcomb(y,j-y);
					to[1][i-j][x-add][j-y]+=from[1][i][x][y]*hcomb(y,j-y);
				}
			}
		}
		swap(from,to);
		
	}
	cout<<ret<<endl;
}

まとめ

DPを横ではなく縦にやるという発想。そこさえ思いつけばあとは余り難しくない。