TopCoderOpen 2018 Round2B Hard SquareFreeSet

解法自体はすぐ思いつくので、むしろ計算量見積もりが本題かも。
http://community.topcoder.com/stat?c=problem_statement&pm=14767

問題

N要素の数列Xが与えられる。
この数列の異なる２要素を選んだ時、その積が平方数にならないようにしたい。

Xのうち１要素を１変化させるのに１コストがかかる。
また、Xの各要素は正の整数でなければならない。
条件を満たすようXを変化させるのに最小コストを求めよ。

解法

f(x) := xを平方数で割り切れるだけ割った値
とすると、(f(X[0]),f(X[1]),...)が異なるようにXを構成すればよい。

各要素同じf(X[i])が取れず、また1だけX[i]を動かすのに1コストがかかるので最小コストフローを使えばよい。
sourceからi番目の頂点に相当する要素に容量1の辺を張り、そこからf(X[i]+j)およびf(X[i]-j)に相当する点にコストjの辺を張る。
f(x)に相当する頂点からsinkに容量1の辺を張ればグラフの出来上がり。
なお、この際jは最大でも2N程度まで見ればよい。

const int prime_max = 1100000;
int NP,prime[100000],divp[prime_max];
map<int,int> M;

void cprime() {
	if(NP) return;
	for(int i=2;i<prime_max;i++) if(divp[i]==0) {
		prime[NP++]=i;
		divp[i]=i;
		for(ll j=1LL*i*i;j>=i&&j<prime_max;j+=i) if(divp[j]==0) divp[j]=i;
	}
}

int gettype(int v) {
	set<int> S;
	while(v>1) {
		int x=divp[v];
		if(S.count(x)==0) S.insert(x);
		else S.erase(x);
		v/=x;
	}
	int ret=1;
	FORR(s,S) ret*=s;
	return ret;
}


template<int NV,class V> class MinCostFlow {
public:
	struct edge { int to, capacity; V cost; int reve;};
	vector<edge> E[NV]; int prev_v[NV], prev_e[NV]; V dist[NV];
	void add_edge(int x,int y, int cap, V cost) {
		E[x].push_back((edge){y,cap,cost,(int)E[y].size()});
		E[y].push_back((edge){x,0, -cost,(int)E[x].size()-1}); /* rev edge */
	}
	
	V mincost(int from, int to, int flow) {
		V res=0; int i,v;
		ZERO(prev_v); ZERO(prev_e);
		while(flow>0) {
			fill(dist, dist+NV, numeric_limits<V>::max()/2);
			dist[from]=0;
			priority_queue<pair<V,int> > Q;
			Q.push(make_pair(0,from));
			while(Q.size()) {
				V d=-Q.top().first;
				int cur=Q.top().second;
				Q.pop();
				if(dist[cur]!=d) continue;
				if(d==numeric_limits<V>::max()/2) break;
				FOR(i,E[cur].size()) {
					edge &e=E[cur][i];
					if(e.capacity>0 && dist[e.to]>d+e.cost) {
						dist[e.to]=d+e.cost;
						prev_v[e.to]=cur;
						prev_e[e.to]=i;
						Q.push(make_pair(-dist[e.to],e.to));
					}
				}
			}
			
			if(dist[to]==numeric_limits<V>::max()/2) return -1;
			int lc=flow;
			for(v=to;v!=from;v=prev_v[v]) lc = min(lc, E[prev_v[v]][prev_e[v]].capacity);
			flow -= lc;
			res += lc*dist[to];
			for(v=to;v!=from;v=prev_v[v]) {
				edge &e=E[prev_v[v]][prev_e[v]];
				e.capacity -= lc;
				E[v][e.reve].capacity += lc;
			}
		}
		return res;
	}
};

MinCostFlow<1100000,int> mcf;


class SquareFreeSet {
	public:
	int findCost(vector <int> x) {
		
		int N=x.size();
		cprime();
		
		int i;
		FOR(i,1100000) mcf.E[i].clear();
		for(i=1;i<=1020000;i++) mcf.add_edge(i,0,1,0);
		FOR(i,N) {
			mcf.add_edge(1050000,1050001+i,1,0);
			for(int j=-200;j<=200;j++) if(x[i]+j>0) {
				mcf.add_edge(1050001+i,gettype(x[i]+j),1,abs(j));
			}
		}
		
		int ret=mcf.mincost(1050000,0,N);
		FOR(i,N) {
			int hoge=0,cost;
			FORR(e,mcf.E[1050001+i]) {
				if(e.to<1050000 && e.capacity==0) {
					hoge=e.to;
					cost=e.cost;
					break;
				}
			}
			cout<<x[i]<<" "<<cost<<" "<<hoge<<" "<<x[i]+cost<<" "<<x[i]-cost<<endl;
		}
		return ret;
	}
}

*まとめ

最大ケースでj=1000でも余裕があったのでそれで入れてしまったが、200でも割とギリギリだった。