yukicoder : No.3213 depth max K

これはすんなり。
https://yukicoder.me/problems/no/3213

問題

整数N,Kが与えられる。
2N文字の正しい括弧列のうち、最も深くネストしている括弧の深さがちょうどK個であるものは何通りか。

解法

f(N,K)を求める解とする。
g(N,K)を、最も深くネストしている括弧の深さK個以下であるものの組み合わせとする。
f(N,K)=g(N,K)-g(N,K-1)となる。

g(N,K)は定めたprefixの文字列長と括弧の深さを状態にとってO(NK)で求められる。

int N,K;
const ll mo=998244353;

ll from[5050],to[5050];

ll hoge(int N,int K) {
	int i,j;
	ZERO(from);
	from[0]=1;
	FOR(i,2*N) {
		ZERO(to);
		FOR(j,K+1) {
			if(j) (to[j-1]+=from[j])%=mo;
			if(j+1<=K) (to[j+1]+=from[j])%=mo;
		}
		
		swap(from,to);
	}
	return from[0];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	ll a=hoge(N,K);
	ll b=hoge(N,K-1);
	cout<<(a+mo-b)%mo<<endl;
}

まとめ

コードも短いね。