またしんどい問題。
https://atcoder.jp/contests/arc128/tasks/arc128_f
問題
N枚のカードがあり、i番目のカードには数値A[i]が書かれている。
1～NのPermutation Pに対し、2名で以下のゲームを行う。
- 2名で交互にカードを取りあう。
- 先手は任意のカードを1枚とる。
- 後手は、残ったカードのうちP[i]が最大となるiを取る。
両者のスコアは、取得したカードの数値の総和となる。
Pの組み合わせ全通りに対し、先手が最適手を取ったときの総スコアを求めよ。
解法
Aを降順に固定する。
まずPが確定したときの最大値を考えよう。Pの逆置換をXとすると、
整数集合Sに対し、
- Xの先頭から2要素を取り除きそのカード番号に対応する数値をSに加える
- 先手は、Sのうち最大値を1つ取得する
ということを繰り返すと最大スコアを得られる。
ここで、「k番目のカードを得られるPは何通りか」ではなく「k番目以前のカードを得られる回数の総和は、P全通りに対し何回か」を考えよう。
f(k) := k番目以前のカードを得られる回数の総和は、P全通りに対し何回か
とすると、解はsum(f(k)*(A[k]-A[k-1]))となる。
上記「先手は、Sのうち最大値を1つ取得する」の各手順でk番目以前のカードを得る組み合わせを考えるとf(k)を求められるが、これだとO(N^2)かかりTLEする。
以下f(k)を考える。
YをY[i]=(X[i]≦k)とした0/1の数列とする。
g(i) := Yの末尾i要素における1の個数
とすると、Pを固定したときにf(k)への寄与はk-max(g(i)-i/2)となる。
k-max(g(i)-i/2)がある値になる組み合わせは、カタラン数の変形で求めることができる。
int N; ll A[1010101]; const ll mo=998244353; const int NUM_=2400001; 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; FOR(i,N) cin>>A[i]; sort(A,A+N); reverse(A,A+N); ll ret=0; /* // O(N^2) for(i=1;i<=N;i++) { ll pat=0; for(int h=max(0,2*i-N);h<=i;h++) { int b=(i-h); int a=N-b; (pat+=(i-(h/2))*(comb(a+b,a)-comb(a+b,a+1)+mo))%=mo; } ll P=pat*fact[i]%mo*fact[N-i]%mo; (ret+=P*(mo+A[i-1]-A[i]))%=mo; } */ FOR(j,2) { ll sum=0; ll add=0; for(i=j;i<=N;i+=2) { (sum+=add)%=mo; if(i*2<=N) { ll a=(comb(N,i)-comb(N,i-2)+mo)%mo; sum+=i*a%mo; (add+=a)%=mo; } //cout<<i<<" "<<add<<" "<<sum<<endl; ll P=sum*fact[i]%mo*fact[N-i]%mo; (ret+=P*(mo+A[i-1]-A[i]))%=mo; if(i*2>=N) { ll a=(comb(N,i)-comb(N,i+2)+mo)%mo; (sum+=mo-(N/2)*a%mo)%=mo; (add+=mo-a)%=mo; } } } cout<<ret<<endl; }
まとめ
O(N^2)まではまだしも、そこからの変形がしんどい。
