PKU演習問メモ(6/12)

PKU
No. 問題名 問題の種類および解法 難易度
3258 River Hopscotch 二分法 ★★★☆☆
2992 Divisors 約数の個数 ★★★☆☆

2992 Divisors

問題概要

n,kが与えられるとき、nCkの約数の個数を求めよ。
0≦n,k≦431であり、答えは64ビットの整数に収まることが保証されている。

解法

基本的に約数の個数を求める問題のセオリーどおり、素因数分解した指数をかけるという方針なのだが、TLEが厳しいため工夫が必要となる。
a = p1^q1 * p2^q2 * ...と素因数分解されるときaの約数の個数は(q1+1)*(q2+1)*...


下コードではn!の各素因数の指数をあらかじめ記録しておくことで、n,kが与えられた時に素因数の候補の個数の回数の掛け算のみで約数の個数を求められるようにした。

ソースコード
int factor[500][500];

int main()
{
	for(int i=2;i<500;i++)
	{
		rep(j,500)factor[i][j]=factor[i-1][j];
		int m=i;
		for(int j=2;j*j<=m;j++)while(m%j==0)factor[i][j]++,m/=j;
		if(m>1)factor[i][m]++;
	}
	
	int n,k;
	while(~scanf("%d%d",&n,&k))
	{
		ll ans=1;
		//nCk=n!/k!/(n-k)!
		rep(i,500)ans*=factor[n][i]-factor[k][i]-factor[n-k][i]+1;
		
		cout<<ans<<endl;
	}
	return 0;
}

3258 River Hopscotch

問題概要

数直線上の[0,L]の区間に（両端のほかに）n個の石が座標x[i]におかれている。
このとき、両端以外から石をm個取り除いて、「最も近い二つの石の距離」を最大にしたい。
そのような最大値を求めよ。

L≦10^9,
n≦50000,
m＜nである。

解法

nが大きいので、i番目までの石で取り除いた数と、最小区間を覚える〜というような動的計画法（O(n^3)？うまくやればO(n^2)くらいになるのだろうか）の解法はおそらく厳しい。


そこで、最小区間の値wを二分法により求ることを考える。
最小区間の幅がw以上であるように石を取り除くことが可能かどうかは、左端の石から、順に幅w内にある石をすべて取り除いていくことでO(n)で判別可能であるため、二分法でそのようなwの最大値を求めることが可能である。


以下のコードでは幅wの石を取り除くところで二分探索を用いているが別に速度的に必要はない。

ソースコード
int l,n,m;
int p[50002];

bool ok(int w)
{
	int cur=0,cnt=0;
	while(cur<n+2)
	{
		int nxt=lower_bound(p+cur+1,p+n+2,p[cur]+w)-p;
		cnt+=nxt-cur-1;
		if(cnt>m)return 0;
		cur=nxt;
	}
	return 1;
}

int main()
{
	scanf("%d%d%d",&l,&n,&m);
	p[0]=0,p[n+1]=l;
	rep(i,n)scanf("%d",p+i+1);
	sort(p,p+n+2);
	
	int hi=l,lo=l,mid;
	rep(i,n+1)lo=min(lo,p[i+1]-p[i]);
	while(hi>lo+1)
	{
		mid=(hi+lo+1)/2;
		if(ok(mid))lo=mid;
		else hi=mid;
	}
	printf("%d\n",lo);
	
	return 0;
}