kmjp's blog

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

Codeforces #612 Div1 D. LCC

問題名は関係なかった。
https://codeforces.com/contest/1286/problem/D

問題

1次元の数直線上にN個のパーティクルがあり、それぞれの初期位置が与えられる。
各パーティクルについて、移動の速さが与えられる。
また左右どちらに動くかの確率が与えられる。

2つのパーティクルが最初に衝突する時刻の期待値を求めよ。

解法

考える衝突は、初期状態で隣接するパーティクル同士のみで良い。
パーティクルの移動の向き毎に、衝突時刻を求め昇順に処理しよう。

SegTreeを使い、パーティクルの区間において、両端のパーティクルの移動の向きが与えられたとき、その中で未衝突となる確率を計算しよう。
処理の際、その状態に至る2パーティクルの状態が最初の衝突となる確率をこのSegTreeを用いて求めることができる。
衝突の時刻と確率の重みづけ平均を取ればそれが解。

int N;
int X[101010],V[101010],P[101010];
const ll mo=998244353;

struct mat{
	ll p[2][2];
};
mat val[1<<19];

mat mul(mat& L, mat& R) {
	mat V;
	int x,y;
	FOR(x,2) FOR(y,2) V.p[x][y]=(L.p[x][0]*R.p[0][y]+L.p[x][1]*R.p[1][y])%mo;
	return V;
}



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

bool cmp(vector<int>& L,vector<int>& R) {
	return 1LL*L[0]*R[1]<1LL*R[0]*L[1];
}

vector<vector<int>> cand;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>V[i]>>P[i];
		val[i+(1<<18)].p[0][0]=val[i+(1<<18)].p[0][1]=(100-P[i])*modpow(100)%mo;
		val[i+(1<<18)].p[1][0]=val[i+(1<<18)].p[1][1]=P[i]*modpow(100)%mo;
	}
	for(i=N;i<1<<18;i++) val[i+(1<<18)].p[1][0]=val[i+(1<<18)].p[1][1]=1;
	for(i=(1<<18)-1;i>=1;i--) val[i]=mul(val[2*i],val[2*i+1]);
	
	
	FOR(i,N-1) {
		if(V[i]<V[i+1]) cand.push_back({(X[i+1]-X[i]),V[i+1]-V[i],i,0,0});
		if(V[i]>V[i+1]) cand.push_back({(X[i+1]-X[i]),V[i]-V[i+1],i,1,1});
		cand.push_back({(X[i+1]-X[i]),(V[i]+V[i+1]),i,1,0});
	}
	sort(ALL(cand), cmp);
	ll ret=0;
	ll pre=0;
	FORR(c,cand) {
		ll P=(val[1].p[0][1]+val[1].p[1][1])%mo;
		i=(c[2]+(1<<18));
		val[i].p[c[3]][c[4]]=0;
		while(i>1) {
			i/=2;
			val[i]=mul(val[2*i],val[2*i+1]);
		}
		ll Q=(val[1].p[0][1]+val[1].p[1][1])%mo;
		P=(P-Q+mo)%mo;
		(ret+=P*c[0]%mo*modpow(c[1]))%=mo;
	}
	
	cout<<ret<<endl;
	
	
	
}

まとめ

なんでこんな問題名にしたんだ。