KUPC2011の簡単なほう

そろそろKUPCなのでKUPCの過去問をやりました。KUPCは特殊形式の良問みたいなのが多くてgood. UTPCよりもいい問題かもしれない。

E: Fpx Number
だめなものを数える。
だめな数nは、

• 素数の2乗の倍数である必要がある。(p^2とする)
• pより小さい素数qにたいして、ord_q(n)

前者は全部ループでまわしてもO(sqrt(A)+B)です。
後者はpが大きくなるごとにそれぞれ更新すればあわせてO(B log B)です。

(計算量自信なし)

コーナーケース：1はFox Numberではありません。(大事)

#include<stdio.h>
#include<algorithm>
using namespace std;
int dm[1100000];
int m[1100000];
int isp[1100000];
int prime[1100000];
int main(){
	int sz=0;
	isp[0]=isp[1]=-1;
	for(int i=2;i<1100000;i++){
		if(~isp[i]){
			isp[i]=1;
			prime[sz++]=i;
			for(int j=i+i;j<1100000;j+=i)isp[j]=-1;
		}
	}
	long long a,b;scanf("%lld%lld",&a,&b);
	long long L=max(1LL,a-b);
	long long R=a+b;
	int n=R-L+1;
	for(int i=0;i<n;i++)m[i]=9999999;
	for(int i=1;(long long)prime[i]*prime[i]<=R;i++){
		int E=prime[i-1];
		for(long long j=(L+E-1)/E*E;j<=R;j+=E){
			long long now=j;
			int time=0;
			while(now%E==0){
				now/=E;time++;
			}
			m[j-L]=min(m[j-L],time);
		}
		int D=prime[i];
		long long S=L/D/D*D*D;
		long long T=R/D/D*D*D;
		while(S<L)S+=(long long)D*D;
		while(T>R)T-=(long long)D*D;
		for(long long j=S;j<=T;j+=(long long)D*D){
			long long now=j;
			int time=0;
			while(now%D==0){
				now/=D;time++;
			}
			if(m[j-L]<time){
			//	printf("%lld %d\n",j,i);
				dm[j-L]=1;
			}
		}
	}
	int ret=n;
	if(L==1LL)dm[0]=1;
	for(int i=0;i<n;i++)if(dm[i])ret--;
	printf("%d\n",ret);
}

F: ボ～ル
まあ幾何パートはいいでしょう。
区間をk個選んで覆える幅の合計を最大化するDPですが、
完全に含まれている区間は選ぶだけ無駄(外側を選んだほうがよい)ので消してよくて、

• • • • • • • • +

+------+
+-----------+
+---+

こんなのからk個選ぶことになります。
i番目を選ぶとき、最大値は
(i番目と全く重なっていないもののなかで最大値)+(i番目の幅)か
(i番目と重なるものの中で最も左にあるやつのコスト)+(あらたに埋まる幅)
のいずれかです。前者はまとめられます。後者は1つしか選択肢がないです。
これでO(NK)です。

#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
double PI=3.14159265359;
int x[2000];
int y[2000];
int r[2000];
pair<double,double> p[2000];
pair<double,double> c[2000];
double dp[2000][2000];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++){
		scanf("%d%d%d",x+i,y+i,r+i);
		double d=sqrt(x[i]*x[i]+y[i]*y[i]);
		double q=atan2(y[i],x[i]);
		if(q<-PI/2)q+=PI*2;
		double v=asin((double)r[i]/d);
		//printf("%f %f\n",(q-v)/PI*180,(q+v)/PI*180);
		p[i]=make_pair(max(0.0,min(PI,q-v)),min(PI,max(0.0,q+v)));
	}
	std::sort(p,p+a);
	int sz=0;
	for(int i=0;i<a;i++){
		bool ok=true;
		for(int j=0;j<a;j++){
			if(i!=j&&p[j].first<p[i].first&&p[i].second<p[j].second)ok=false;
		}
		if(ok){
			c[sz++]=p[i];
		}
	}
	double ret=0;
	for(int i=1;i<=b;i++){
		double tmp=0;
		int at=0;
		for(int j=0;j<sz;j++){
			while(c[at].second<c[j].first){tmp=max(tmp,dp[i-1][at]);at++;}
			dp[i][j]=max(tmp+c[j].second-c[j].first,dp[i-1][at]+c[j].second-c[at].second);
			ret=max(ret,dp[i][j]);
		}
	}printf("%.12f\n",ret/PI);
}