kmjp's blog

競技プログラミング参加記です

Codeforces #239 Div1 C. Curious Array

Codeforces

本番中は答えまで行かなかったけど、これも落ち着いて解けばそこまでトリッキーではないな。
http://codeforces.com/contest/407/problem/C

問題

初期状態として整数配列A[i]が与えられる。
ここでM個のクエリを適用する。

各クエリiはL[i]、R[i]、K[i]で構成されており、L[i] <= j <= R[i]となる各jにおいてA[j]に {}_{j-L_i+K_i} C_{K_i}を加算する。
最終的なA[i]の値を答えよ。

解法

与えられたA[i]の値は途中のクエリには影響しない。
よって配列が空の状態から初めて最後に与えられたA[i]を足せばよい。

例えば"6 8 2"というクエリではA[6]～A[8]にC[2][2]、C[3][2]、C[4][2]を加算することになる。
パスカルの3角形を45度回転させ、P[r][c]+=P[r-1][c]+P[r][c-1]とする。
下の2つの行列の上側のようにP[0][0]だけ1を置いた場合、漸化式を適用すると下のようにi列目にC[i-1][i-1]、C[i][i-1]、C[i+1][i-1]…が生成されることがわかる。

1 0 0 0 0
0 0 0 0 0
0 0 0 0 0

1 1 1 1 1
1 2 3 4 5
1 3 6 10 15

欲しいのはC[2][2]～C[4][2]だけでC[5][2]以降は要らないので、以下のようにC[2][2]～C[4][2]の負の値を置いておくと以下のようにC[2][2]～C[4][2]だけが最下段で加算される。

1 0 0 -1 0
0 0 0 -3 0
0 0 0 -6 0

1 1 1 0 0
1 2 3 0 0
1 3 6 0 0

これだけ見るとC[2][2]～C[4][2]を置いてC[2][2]～C[4][2]を得ているだけだが、実際はK[i]<=100なので置く数は100以下であり、L[i]～R[i]は10^5あるので100個以下の箇所だけ配列要素をいじるだけで最終的にL[i]～R[i]個の解が得られる。

よって、あとは各クエリにおいてP[r][c]の適切な場所に1加算したうえでそれを打ち消す負の値をK[i]+1個配置する。
最後にP[r][c]+=P[r-1][c]+P[r][c-1]を実行すればよい。

int N,M;
const int NN=100500;
const int D=105;

ll A[NN];
ll C[D+NN+1][D+1];
ll V[D+NN+1][D+1];
ll mo=1000000007;

void solve() {
	int f,i,j,r,k,l,x,y;
	
	cin>>N>>M;
	FOR(i,N) cin>>A[i];
	C[0][0]=1;
	for(i=1;i<=D+NN;i++) {
		C[i][0]=1;
		for(j=1;j<=D;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mo;
	}
	
	while(M--) {
		cin>>l>>r>>k;
		l--;
		V[D-k+l][D-k]++;
		for(i=D-k;i<=D;i++) V[i+r][i]+=mo-C[r-l-1+i-(D-k)][i-(D-k)],V[i+r][i]%=mo;
	}
	
	for(i=1;i<=D+NN;i++) {
		V[i][j]=((V[i][j]+V[i-1][j])%mo+mo)%mo;
		for(j=1;j<=D;j++) V[i][j]=((V[i][j]+V[i-1][j]+V[i-1][j-1])%mo+mo)%mo;
	}
	FOR(i,N) _P("%lld ",(V[D+i][D]+A[i])%mo);
	_P("\n");
}

まとめ

本番パスカルの三角形からうまく生成するんだろうなとは思ったけど、うまい配列配置ができなかった。
問題文自体はあっさりだけど、解法は面白い問題。