kmjp's blog

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

Codeforces #752 Div1 : D. Artistic Partition

解法ありきで作られた問題っぽいな。
https://codeforces.com/contest/1603/problem/D

問題

整数[L,R]に対し、C(L,R)はL以上R以下の順序なし整数対(i,j)のうち、GCDがL以上となるものを示す。

以下の問いに答えよ。
整数N,Kが与えられる。
初項が0、末尾がKである、N要素の単調増加な整数列X全通りを考える。
それぞれにおいて、C(X[i]+1,X[i+1])の総和の最小値

解法

R<L*2の場合、C(L,R)は1にしかならない。
よって、Xを(0,1,3,7,15,....)とすると取りえずC(a,b)は常にi=jの時だけカウントしてb-a+1となる。
なので、K≧logNの場合、解はN。

Kが18以下の場合、分割統治の要領で分割位置を列挙していこう。

int T;
int K,N;
ll phi[101010];
ll PS[101010];
ll dp[103030][20];


ll add[303030];

ll sum(int L,int R) {
	ll ret=0;
	while(L<=R) {
		ll nex=min(R,R/(R/L));
		ret+=(nex-L+1)*PS[R/L];
		L=nex+1;
	}
	
	return ret;
}

void dfs(int step,int L,int R,int X,int Y) {
	if(L>R) return;
	int M=(L+R)/2;
	int tar=-1;
	int i;
	ll CS=sum(X+1,M);
	for(i=X;i<=min(M-1,Y);i++) {
		if(dp[i][step-1]+CS<dp[M][step]) {
			dp[M][step]=dp[i][step-1]+CS;
			tar=i;
		}
		CS-=PS[M/(i+1)];
	}
	
	dfs(step,L,M-1,X,tar);
	dfs(step,M+1,R,tar,Y);
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	for(i=1;i<=100000;i++) phi[i]=i;
	for(i=1;i<=100000;i++) {
		for(j=i*2;j<=100000;j+=i) phi[j]-=phi[i];
		PS[i]=PS[i-1]+phi[i];
	}
	for(i=1;i<=100000;i++) FOR(j,18) dp[i][j]=1LL<<60;
	for(i=1;i<=17;i++) dfs(i,1,100000,0,100000);
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		
		if(K>=18) {
			cout<<N<<endl;
		}
		else {
			cout<<dp[N][K]<<endl;
		}
	}
}

まとめ

解法ありきな問題すぎるのは余り好きではないな…。