kmjp's blog

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

Codeforces #341 Div2. C. Wet Shark and Flowers

なんか最近CF Div2回ミスが多すぎる…。
http://codeforces.com/contest/621/problem/C

問題

N人の人が円周上に並んでいる。
各人L[i]~R[i]の間のいずれかの整数を等確率でランダムに選択する。

i番の人の数値と(i+1)番の選んだ数値の積が素数Pの倍数である場合、2人に1000ずつポイントが入る。
全員の総ポイントの期待値を求めよ。

解法

Pは素数なので、i番と(i+1)番のどちらかがPの倍数を取れば、2人で合計2000pt得られる。
i番の人がPの倍数を取る確率をF(i)とすると、各iに対し1-(1-F[i])*(1-F[i+1])の確率で2000pt得られることになる。
後は上記数式を各iに対して合算するだけ。

int N;
ll P;
int L[101010],R[101010];
double H[301010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>P;
	FOR(i,N) {
		cin>>L[i]>>R[i];
		H[i+N]=H[i]=(R[i]/P-(L[i]-1)/P)*1.0/(R[i]-L[i]+1);
	}
	
	double ret=0;
	FOR(i,N) ret+=1-(1-H[i])*(1-H[i+1]);
	_P("%.12lf\n",ret*2000);
}

まとめ

Bの方が一瞬迷って難しい気が?