Codeforces #708 Div2 : E2. Square-free division (hard version)

最終問の割にすんなり。
https://codeforces.com/contest/1497/problem/E2

問題

整数列Aが与えられる。
これをいくつかの連続部分列に分割することを考える。
この時、各部分列内で、2要素の積が平方数になってはならない。

最大K個までAの要素を任意の値に書き換えられるとき、最小何個の部分列に分割できるか。

解法

先にAの各要素を平方数で割っておけば、積が平方数という条件は、単に同じ値を2個含まないという簡単な条件に置き換えられる。
あとは、

• 各要素を部分列の左端とするとき、k個値を書き換えたときに右端をどこまで伸ばせるか
• 各要素から始まるsuffixを、k個まで値を書き換えたとき最小何個の部分列に分割できるか

をそれぞれ後ろから更新していけばよい。

int T;
int N,K;
int A[202020];
int nex[202020];
int dp[202020][21];
int step[202020][21];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>K;
		
		FOR(i,N) {
			cin>>A[i];
			for(j=2;j*j<=A[i];j++) {
				while(A[i]%(j*j)==0) A[i]/=j*j;
			}
		}
		map<int,int> ne;
		
		FOR(i,21) dp[N][i]=N, step[N][i]=0;
		for(i=N-1;i>=0;i--) {
			if(ne.count(A[i])) {
				nex[i]=ne[A[i]];
			}
			else {
				nex[i]=N;
			}
			ne[A[i]]=i;
			
			FOR(j,21) {
				dp[i][j]=min(nex[i],dp[i+1][j]);
				if(j) dp[i][j]=max(dp[i][j],dp[i+1][j-1]);
			}
			
			FOR(x,21) step[i][x]=1<<20;
			FOR(j,21) for(x=0;x<=j;x++) step[i][j]=min(step[i][j],1+step[dp[i][x]][j-x]);
		}
		cout<<step[0][K]<<endl;
	}
}

まとめ

難しくはないけどちょこちょこ面倒。