PKU演習問メモ(9/14)

PKU

漸く書いてなかった分の解説書けたorz

No. 問題名 問題の種類および解法 難易度
3684 Physics Experiment 弾性衝突 ★★★☆☆
3276 Face The Right Way 貪欲法 ★★★★☆
3320 Jessica's Reading Problem 尺取メソッド ★★★☆☆
1064 Cable master 二分法 ★★★☆☆
1127 Jack Straws 線分の交差判定・Union-Find ★★★☆☆

3684 Physics Experiment

問題概要

半径rの同じn個のボールが高さHの場所にある筒に入れられている。
これらを1秒毎に1つずつ落とす。ボール同士、ボールと床がぶつかった場合完全弾性衝突して互いの速度が入れ替わる。


最初のボールを離してからt秒後の、それぞれのボールの高さを求めよ。

解法

ぱない本参照。なんか通らないと思って、コード写したが、それでも通らなくてだんだん丸写し度が100%に近づいていっても通らないから悩んだらif(T<0)の条件入れ忘れてたという罠。はがが。

ソースコード
int n,h,r,T;
double calc(int T)
{
	if(T<0)return h;
	double t=sqrt(h/5.0),r;
	int k=int(T/t);
	if(k%2==0)r=T-t*k; else r=t*k+t-T;
	return h-5.0*r*r;
}
int main()
{
	int cs; scanf("%d",&cs);
	while(cs--)
	{
		scanf("%d%d%d%d",&n,&h,&r,&T);
		double y[100];
		rep(i,n)y[i]=calc(T-i);
		sort(y,y+n);
		rep(i,n)printf("%.2f%c",y[i]+i*r*0.02,(i==n-1?'\n':' '));
	}
	return 0;
}

3276 Face The Right Way

問題概要

n頭の牛がいる。それぞれ後ろまたは前を向いている。長さkの牛反転機を使うと、k頭の牛の向き（前後）を同時に入れ替えることができる。
牛反転機を使う最小回数と、そのときの牛反転機の長さを求めよ。

n≦5000を満たす。

解法

ぱない本で解説されていた方法で。このブログ読んでる人で買ってない人とかいなさそうだし解説適当でいいよね……


反転機を使う順序は関係ないので、左から使うとしてよい。
現在の牛が反転されてなかった場合その牛に反転機を使う必要がある。


反転機を使った場合、フラグを立てておき、暫くたった後でフラグを回収する。（何のこっちゃ）

ソースコード
int n;
bool fb[5000],f[5000];

int main()
{
	scanf("%d",&n);
	char c;
	rep(i,n)scanf(" %c",&c),fb[i]=c=='B';
	
	int mn=inf,mnk=inf;
	for(int k=1;k<=n;k++)
	{
		bool t=0; int m=0;
		rep(i,n)f[i]=0;
		
		rep(i,n)
		{
			if(fb[i]^t)
			{
				if(i<=n-k)f[i]=1,t^=1,m++;
				else goto FAIL;
			}
			if(i>=k-1)t^=f[i-k+1];
		}
		if(mn>m||mn==m&&mnk>k)mn=m,mnk=k;
		FAIL:;
	}
	printf("%d %d\n",mnk,mn);
	return 0;
}

3320 Jessica's Reading Problem

問題概要

Pページからなる本があり、それぞれのページに書かれた内容はp[i]である。
内容には重複があるため、連続するkページで、本に書かれた内容全てが書かれているページだけを読むことにしたい。


そのような最小のkを求めよ。


P≦1000000,p[i]は32ビット整数に収まるとしてよい。

解法

p[i]が大きいので座標圧縮的なことをして、小さな量にする。
次に尺取メソッドをしながら、全てのページが書かれているときにansを更新していく。

ソースコード
int n,p[1000000];
int m,v[1000000],cnt[1000000];


int main()
{
	scanf("%d",&n);
	rep(i,n)scanf("%d",p+i),v[i]=p[i];
	sort(v,v+n); m=unique(v,v+n)-v;
	
	rep(i,n)p[i]=lower_bound(v,v+m,p[i])-v;
	int r=0,c=0,ans=inf;
	rep(i,n) //iページ目からrページ目までを読む
	{
		for(;r<n&&c<m;r++) //内容が足りない場合もっと読む
		{
			cnt[p[r]]++;
			if(cnt[p[r]]==1)c++;
		}
		if(c<m)break;
		
		ans=min(ans,r-i); //左側のページを読まなくする
		cnt[p[i]]--;
		if(cnt[p[i]]==0)c--;
	}
	printf("%d\n",ans);
	
	return 0;
}

1064 Cable master

問題概要

n本のロープがあり、それぞれの長さはl[i]である。
ここから長さの等しいk本のロープを切り出したい。
そのようなもののうち、可能な最大の長さを求めよ。


n,k≦10000を満たす。

解法

誤差の判定され方がなんか変。100倍して切捨てして1/100にしないとダメな模様。
しかもeps=0.0001でやったらなぜかWAった。


二分法の典型問。長さaのロープを切り出せるかどうかはO(n)で判定できるため、これを収束するまで繰り返す。

ソースコード
int n,k;
double l[10000];

bool ok(double a)
{
	int ret=0;
	rep(i,n)ret+=int(l[i]/a);
	return ret>=k;
}
int main()
{
	scanf("%d%d",&n,&k);
	rep(i,n)scanf("%lf",l+i);
	double lo=0,hi=INF,mid;
	rep(i,100)
	{
		mid=(lo+hi)/2;
		if(ok(mid))lo=mid; else hi=mid;
	}
	printf("%.2f\n",floor(lo*100)/100.0);
	
	return 0;
}

1127 Jack Straws

問題概要

線分で表されるn本の藁がある。
それぞれの藁の両端点(x1,y1),(x2,y2)が与えられるとき、与えられた二つの藁が直接または間接的に繋がっているかどうかを判定せよ。


ただし、繋がっているとは、線分が共有点を持つことを言う。
n＜13を満たす。

解法

union-findを使えばよい。
それぞれの藁が共有点を持つ場合にそれらをunionする。
線分の交差判定はspaghetti sourceのコードを使用。

ソースコード
int n;
int p[13];
int root(int x)
{
	if(p[x]==x)return x;
	return p[x]=root(p[x]);
}
void merge(int x,int y)
{
	x=root(x); y=root(y);
	if(x!=y)p[y]=x;
}
int main()
{
	while(scanf("%d",&n),n)
	{
		rep(i,n)p[i]=i;
		
		vector<L> l;
		int x1,y1,x2,y2;
		rep(i,n)
		{
			scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
			l.pb(L(P(x1,y1),P(x2,y2)));
		}
		rep(i,n)rep(j,i)if(intersectSS(l[i],l[j]))merge(i,j);
		
		int x,y;
		while(scanf("%d%d",&x,&y),x)
		puts(root(x-1)==root(y-1)?"CONNECTED":"NOT CONNECTED");
	}
	return 0;
}