AtCoder ARC #145 : C - Split and Maximize

不参加だった回。
https://atcoder.jp/contests/arc145/tasks/arc145_c

問題

正整数Nが与えられる。
1～2Nの順列Pに対し、Pのスコアは、Pを2つのN要素の数列A,Bに順序を保って分割したとき、AとBのドット積の最大値とする。
Pの全パターンのうち、スコアが最大値となるのは何通りか。

解法

スコアの最大値は自明で、2n-1と2nが積を取るようにA,Bを配置することである。
これは、2N文字の括弧列を考え、開き括弧と閉じ括弧の位置に2nと2n-1を配置できれば、2n-1と2nを掛け合わせるような分割が可能。
括弧のパターンはカタラン数で計算でき、そこに2n-1と2nのどちらを前に持ってくるかで2^Nパターン掛けたものが解。

int N;
const ll mo=998244353;

const int NUM_=440001;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
ll comb(ll N_, ll C_) {
	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;
	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;
	
	cin>>N;
	ll a=(mo+comb(2*N,N)-comb(2*N,N-1))%mo;
	a=a*fact[N];
	FOR(i,N) a=a*2%mo;
	cout<<a<<endl;
	
}

まとめ

2つの数列に分割するのを、括弧列で表現するテクは良いな。
覚えておこう…。