Cで苦戦しまくってしまった。
https://atcoder.jp/contests/dwacon6th-prelims/tasks/dwacon6th_prelims_b
問題
N体のスライムが1次元の座標上X[i]に並んでいる。
残されたスライムのうち、もっとも右以外の物を1つ選択し、最寄の右のスライムのところまで移動して消すという作業を、残り1体になるまで繰り返す。
スライムの選択順(N-1)!通りにおいて、スライムの移動量の総和を求めよ。
解法
初期状態でi番目にスライムがj番目のところまで移動する確率は、
- j番が最も右ならi~(j-1)番のうちi番が最後に選択される1/(j-i)。
- j番が最も右でなければ、i~j番のうちj番が最後、ii番が最後から2番目に選択される1/((j-i)*(j-i+1)
前者の移動量の期待値はiを総当たりしつつ(X[j]-X[i])/(j-i)を求めればよいのでO(N)で済む。
後者でいえば、移動量の期待値は(X[j]-X[i])/((j-i)*(j-i+1)となる。こちらはi,jを愚直に総当たりするとO(N^2)となる。
ただ、X[j]に着目するとiがj以下の範囲で移動するとしてX[j]*(1/(1*2)+1/(2*3)+....)という簡単な形になる。X[i]も同様。
なので後ろの分数の加算部分を先に累積和を取っておけばO(N)で求めることができる。
int N; int X[101010]; const ll mo=1000000007; const int NUM_=400001; static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1]; ll sum[101010]; ll comb(ll N_, ll C_) { if (fact[0]==0) { 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; } 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; comb(1,1); cin>>N; FOR(i,N) cin>>X[i]; for(i=1;i<=N;i++) { sum[i]=(sum[i-1]+inv[i]*inv[i+1])%mo; } ll ret=0; y=N-1; FOR(x,y) { (ret+=inv[y-x]%mo*(X[y]-X[x]))%=mo; } FOR(x,N-1) { if(x) (ret+=X[x]*sum[x])%=mo; ret+=mo-X[x]*sum[N-2-x]%mo; } ret=(ret%mo+mo)%mo; cout<<ret*fact[N-1]%mo<<endl; }
まとめ
まぁこれはそこまで苦労しなかった。