Codeforces ECR #145 : G. Prediction

コードは短い。
https://codeforces.com/contest/1809/problem/G

問題

N人の勝ち抜き戦を考える。
これはN人を並べ、先頭の2名が試合をして勝った方が再び列の先頭に戻る、ということを(N-1)回行い、最後に残った人が勝者となる。
各人にはレートが設定されており、その差がKより大きければ大きい方が勝ち、K以下ならばどちらが勝つかわからない。

N人の並べ方N!のうち、全試合の勝者が確定する並びは何通りか。

解法

挿入DPで、レートの大きい順に並びを決めていく。
dp(n) := n要素目まで決めたとき、先頭要素が条件に違反しない並び方

とすると、dp(n)に対し、(n+1)要素目を先頭か先頭以外に置くかで分岐する。
条件を満たす必要があるのは先頭に置くときだけなので、その際同時にn+1番以降で差がK以下の人の位置を同時に決めてしまうとよい。

int N,K;
ll A[1010101];
const ll mo=998244353;
ll dp[1010101];
int ok[1010101];

const int NUM_=2000003;
static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];

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>>K;
	FOR(i,N) cin>>A[i];
	reverse(A,A+N);
	if(A[0]-A[1]>K) dp[1]=1;
	for(i=1;i<N;i++) {
		if(i) ok[i]=ok[i-1];
		while(ok[i]<N&&A[i]-A[ok[i]]<=K) ok[i]++;
		int conf=ok[i]-i-1;
		
		//先頭以外ならどこでも
		(dp[i+1]+=dp[i]*i)%=mo;
		
		//先頭に置くなら、ぶつかる奴は後ろに置く
		(dp[i+conf+1]+=dp[i]*fact[i+conf+1-2]%mo*factr[i-1])%=mo;
	}
	cout<<dp[N]<<endl;
	
}

まとめ

コードは短いけど、この状態遷移さっと出ないなぁ。