2013-04-11

■ Codeforces 268E & 271E 16:02

最近解きました。両方とも学ぶことの多い良問でした。

268E: "Playlist"

http://d.hatena.ne.jp/DEGwer/20130313/1363161745 <-これをみて知りました

要約:歌がN個ある。全ての歌について長さと気に入る確率がわかっている。

Manaoという人は歌を聞き、もし気に入らないと今まで聞いた歌のうち気に入ったものをすべて聞く変人です。

聞いた歌の長さの期待値の最大値を求めよ。

方針:隣り合う二曲(S1,S2とする)の長さ、気に入る確率をL1,L2,P1,P2とすると、

S1を先に聞いた時の期待値-S2を先に聞いた時の期待値=L1*P1*(1-P2)-L2*P2*(1-p1)になる。

しかしこのままでは、比較する値にP1,P2という数があるので50000^2/2種類を

いちいち計算する必要があり時間の問題で不可不可

ところで、 L1*P1*(1-P2)とL2*p2*(1-P1)の関係は L1*P1/(1-P1)とL2*P2/(1-P2)と同じである。

(P1!=1 && P2 !=1)よって、条件を満たす並べ方(p1p2...pN)において

Lp1*Pp1/(1-Pp1)>Lp2*Pp2/(1-Pp2)...>LpN*PpN/(1-PpN)であるため

ソートしてhogehogeすればよい〜〜〜O(N log N)

もし気に入る確率 is 100%ならLx*Px/(1-Px)にINFをなげましょう

ソース

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef double d;
typedef pair P;
typedef pair P1;
typedef pair P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
int main(){
	int Number;
	cin >> Number;
	priority_queueque;
	for(int i=0;idouble len,prob; cin >> len >> prob;
		que.push(mp(len*prob/((100.0-prob)!=0.0?(100.0-prob):0.001),mp(len,prob)));
	}
	double MaximumExpectedLength=0.0,ExpectedRepeatLength=0.0;
	while(!que.empty()){
		P1 p1=que.top(); que.pop();
		MaximumExpectedLength+=p1.second.first;
		MaximumExpectedLength+=ExpectedRepeatLength*(100.0-p1.second.second)/100.0;
		ExpectedRepeatLength+=p1.second.first*p1.second.second/100.0;
	}
	printf("%.10lf\n",MaximumExpectedLength);
	return 0;
}

271E "Three Horses"

要約:三匹の馬たちがいる。また、自然数二つで表せるカードがあります。(つまり(a,b)のように表す)

三匹はそれぞれ能力を持っており、

1匹目は(a,b)を見せると->(a+1,b+1)というカードを作ってくれ、

2匹目は(a,b)(a,bは偶数)を見せると->(a/2,b/2)というカードを作ってくれ、

3匹目は(a,b),(b,c)を見せると->(a,c)というカードを作ってくれます。

Polycarpusという変な人がいて、(1,A1),(1,A2)...(1,AN)というN枚のカードを作りたがっている。

1枚のカード(x,y)(1<= x < y <= m)のうち、それをみせてN枚全て作成可能であるものは何種類あるか。

方針:

とりあえず以下を示す:

特定のYについて,

(X,X+Y)が作成であるXが1つでも見つかれば、

カードを表す2つの数の差がYである任意のペアのカードが作れる

証明:(A,A+S)が作れたとする。一匹目に何度か投げると(A+S,A+2S)がつくれる。これを三匹目に投げると(A,A+2S)が得られる。

Aが偶数なら二匹目に投げて(A/2,A/2+S),そうでなくても((A+1)/2,(A+1)/2+S)にできる。

すると、A>=2のとき必ず左の値は必ず減少するため、この操作をくり返すことによって、(1,S+1)を作れる。

あとは一匹目に投げれば任意のカードが生やせる。

よって、カードを考える時は右-左だけ考えればよい。

次に、右-左=Xのカードを生やすには右-左がどんな数のカードでなければいけないか考える。

一匹目に投げた時、差は変化しない。

二匹目に投げた時、差は半分になる。

三匹目に投げた時、二枚のカードの差の合計になる。

よって、差がXの約数ならよいことがわかる。

また、2の冪乗は二匹目に投げ続けるとなくすことができるので

結局2の冪乗*Xの約数ならok.

N枚のカードを作る操作はそれぞれ独立に作っていく時と何も変わらないので、

差が 2の冪乗*(A1-1)の約数,2の冪乗*(A2-1)の約数...2の冪乗*(AN-1)の約数で表せるカードならok.

これは2の冪乗*GCD( (A1-1),(A2-1),...,(AN-1) )の約数である。

この数はせいぜい30*(10^9以下の自然数における最大の約数の個数)個しかないので１つ１つ見ていくことができる。

差がsのペアはm-s個あることがわかっているので後はゴリゴリ書く。

ソース

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
typedef double d;
typedef pair P;
typedef pair P1;
typedef pair P2;
typedef long long l;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 2000000000
l gcd(l a,l b){
	if(a%b) return gcd(b,a%b);
	else return b;
}
int main(){
	int n,m; l cur;
	scanf("%d %d",&n,&m);
	scanf("%lld",&cur);
	cur--;
	for(int i=1;i"%lld",&d); d--;
		cur=gcd(max(cur,d),min(cur,d));
	}
	while(cur%2==0) cur/=2; long long bit[32];
	bit[0]=1; for(int i=1;i<32;i++) bit[i]=bit[i-1]*2;
	long long ret=0,sum=0;
	for(int i=1;i*i<=cur;i++){
		if(cur%i==0){
			l k=cur/i;
			for(int j=0;j<32;j++){
				if(bit[j]*i>m){
					ret+=j;
					sum+=(bit[j]-1)*i;
					break;
				}
			}
			if(k!=i){
				for(int j=0;j<32;j++){
				if(bit[j]*k>m){
					ret+=j;
					sum+=(bit[j]-1)*k;
					break;
				}
				}
			}
		}
	}
	printf("%lld",ret*m-sum);
	return 0;
}

以上です。

今夜のCFは2完したいな

ツイートする