AtCoder ARC #204 : A - Use Udon Coupon

A問題から割と手間取った…。
https://atcoder.jp/contests/arc204/tasks/arc204_a

問題

N要素の整数列A,Bと、空のキューQと、初期値0の変数C、初期値1の変数iがある。
以下のいずれかの処理を合計2N回行う。

• iがN以下の時、Cをmax(0,C-A[i])で置き換え、Qの末尾にiを追加する
• Qが空でないとき、先頭の値をiとするとCをC+B[i]で置き換え、Qの先頭要素を削除する。

処理の順番のうち、Cの最終的な値がL以上R以下となるのは何通りか。

解法

1つ目の処理のmaxを取る部分を無視して考えると、初期値はC=0で、最後はC=sum(B)-sum(A)になる。
また、前者の処理をa回、後者をb回行っているなら、S(a,b)=sum(B[1...b])-sum(A[1...a])とおくとその時C=S(a,b)となる。
もち途中Cの最小値がMの場合、Cは-Mだけ大きくなるので、C=sum(B)-sum(A)-Mとなる。

言い換えれば、L≦sum(B)-sum(A)-M≦Rであり、sum(B)-sum(A)-R≦M≦sum(B)-sum(A)-Lである。

dp(a,b,x) := 前者をa回、後者をb回行う手順のうち、S(a,b)≧sum(B)-sum(A)-Rとなる状態のみを経由して至る手順の数。途中、xはsum(B)-sum(A)-R≦S(a,b)≦sum(B)-sum(A)-Lとなる状態を経由したことがあるかどうかの真偽値
としてDPのテーブルを埋め、dp(N,N,true)を回答すればO(N^2)で回答できる。

int N,L,R;
int A[5050],B[5050];
int SA[5050],SB[5050];
const ll mo=998244353;

int D[5050][5050];
ll dp[5050][5050][2];

ll comb(ll N_, ll C_) {
	const int NUM_=400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>R;
	FOR(i,N) {
		cin>>A[i];
		SA[i+1]=SA[i]+A[i];
	}
	FOR(i,N) {
		cin>>B[i];
		SB[i+1]=SB[i]+B[i];
	}
	FOR(y,N+1) FOR(x,N+1) D[y][x]=SB[x]-SA[y];
	int S=D[N][N];
	int mi=S-R,ma=S-L;
	
	ll ret=0;
	dp[0][0][D[0][0]>=mi&&D[0][0]<=ma]=1;
	FOR(y,N+1) FOR(x,N+1) FOR(i,2) {
		if(y+1<=N&&D[y+1][x]>=mi&&y+1>=x) (dp[y+1][x][i|(D[y+1][x]<=ma)]+=dp[y][x][i])%=mo;
		if(x+1<=N&&D[y][x+1]>=mi&&x+1<=y) (dp[y][x+1][i|(D[y][x+1]<=ma)]+=dp[y][x][i])%=mo;
	}
	
	
	
	cout<<dp[N][N][1]<<endl;
	
	
}

まとめ

もう少しすんなり解きたかったな。