kmjp's blog

競技プログラミング参加記です

第6回 ドワンゴからの挑戦状 予選 : B - Fusing Slimes

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;
	
}

まとめ

まぁこれはそこまで苦労しなかった。