AtCoder ARC #186 (AtCoder Japan Open -予選-) : D - Polish Mania

本番もうちょっとだったのにな…。
https://atcoder.jp/contests/arc186/tasks/arc186_d

問題

非負整数列VがPolishであるとは、以下のように定義する。

• V[0]の後に、V[0]個のPolishな数列が連結した状態
• V=(0)はPolishである。

長さNの非負整数列Aが与えられる。
長さNのPolishな非負整数列Ⅴのうち、辞書順でA以下のものは何通りか。

解法

2次元座標上で、初期状態(1,0)にある点が、右や上の隣接する格子点に移動しながら、(N,N)に到達する経路を考える。
この際、最後の(N,N)を除きy=x上を通過してはならない。

こうすると、この移動経路に対し、Polishな数列Vは1上に移動する間に右に移動した回数を列挙した数列に対応付けられる。
よってその組み合わせはカタラン数の要領で数えられる。

Aの値に沿って点を(1,0)から動かすことを考える。
V[0...(i-1)]=A[0,...(i-1)]であり、V[i]＜A[i]となるケースを数え上げる。
現在地が(x,y)にある場合、V[i]＜A[i]であるということは、(x,y)→(N,N)に至るケースから、(x+A[i],y)を通るケースを引けばよい。
その後、現在地を(x+A[i],y+1)にずらして、A[i+1]について同様に見て行くとよい。

int N;
int A[303030];
const ll mo=998244353;
const int NUM_=1400001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

ll dp[20][20];

ll comb(ll N_, ll C_) {
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

ll catalan_arrange(int X,int Y,int T=1) {
	if(X+T<=Y||X<0||Y<0) return 0;
	return (comb(X+Y,Y)-comb(X+Y,Y-T)+mo)%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	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;
	
	ll ret=0;
	cin>>N;
	int cx=1;
	int cy=0;
	
	FOR(i,N) {
		cin>>x;
		
		ret+=catalan_arrange(N-cy-1,N-cx,1);
		if(cx+x<=N) ret+=mo-catalan_arrange(N-cy-1,N-(cx+x),1);
		
		
		cx+=x;
		cy++;
		if(cx>N) break;
		if(cy>=cx) break;
		
	}
	if(cx==N&&cy==N) ret++;
	cout<<ret%mo<<endl;
	
	
}

まとめ

カタラン数と関係があるところまでは行ったけど、Vとの対応付けが整理しきれていなかった。