CodeQUEEN 2026 決勝 : G - きみの愛馬は？

これはまぁどうにか。
https://atcoder.jp/contests/codequeen2026-final-Public/tasks/codequeen2026_g

問題

整数N,Kと昇順の整数列Xが与えられる。
1～Nの整数のうちK個を選び昇順に並べた整数列を考える。
整数列A,Bを並べるとき、A[i]≦B[i]が常に成り立つならAはBの手前になければならない。そうでない場合は、どちらが前でも良い。

整数列Xは、最大・最小で何番目になりうるか。

解法

最小の方を考えると、Y≦XとなるYを数え上げればよい。
逆に最大の方は、C(N,K)からX≦YとなるYを引けばよく、これは同じような考え方で解ける。

以後前者の解き方を考える。
dp(n,m) := Yのn要素目まで決めたとき、Y[n]はX[m-1]+1以上X[m]以下であるような組み合わせ

とする。
X[y-1]+1～X[y]の範囲をYに何個入れるかを考えると、
dp(x,y) += dp(n,m) * C(X[y]-X[y-1], n-x) (ただしx＞n、y＞m)
のように遷移する。
mに関しては累積和を取りながらdp(x,y)を求めて行こう。

int N,K;
int X[303];
const ll mo=998244353;

ll num[313][313];
ll dp[313][313];

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

ll hoge(vector<ll> X) {
	X.insert(X.begin(),0);
	X.push_back(N);
	int i,j,l;
	FOR(i,K+1) {
		ll p=1,q=1;
		for(j=1;j<=K;j++) {
			p=p*(X[i]-X[i-1]+1-j)%mo;
			q=q*j%mo;
			num[i][j]=p*modpow(q)%mo;
		}
	}
	ZERO(dp);
	dp[0][0]=1;
	FOR(i,K) {
		ll sum=0;
		FOR(j,i+1) {
			(sum+=dp[i][j])%=mo;
			for(l=1;i+l<=K;l++) {
				(dp[i+l][j+1]+=sum*num[j+1][l])%=mo;
			}
		}
	}
	ll ret=0;
	FOR(j,K+2) (ret+=dp[K][j])%=mo;
	return ret;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	vector<ll> A,B;
	FOR(i,K) {
		cin>>x;
		A.push_back(x);
		B.push_back(N+1-x);
	}
	reverse(ALL(B));
	ll sum=1;
	FOR(i,K) sum=sum*(N-i)%mo*modpow(i+1)%mo;
	
	cout<<hoge(A)<<" "<<(sum+mo-hoge(B)+1)%mo<<endl;
}

まとめ

馬の設定はどこから来たんだろうな。