Codeforces #259 Div1 B. Little Pony and Harmony Chest

数の制限は小さいが結構時間を食う問題。
http://codeforces.com/contest/453/problem/B

問題

正の整数からなる数列B[i]が調和しているとは、どの2要素をとってもそれが互いに素である数列をさす。
ここで数列A[i]が与えられる。
A[i]と同じ要素数の調和した数列B[i]のうち、A[i]との差、すなわちが最小となるものを答えよ。

解法

B[i]を全部1にすれば明らかに調和する。
A[i]<=30なので、B[i]は58以下である。
よってA[i]を降順ソートし、B[i]の候補を58から降順で割り当てていけばよい。

事前に1～58までの数字が互いに素かどうかbitmaskを用意しておき、利用可能な数値のbitmaskを更新しながらDFSしていく。

int N,A[101];
ll mat[61];
pair<int,int> P[101];

int mi;
int mip[101];
int cup[101];

void dfs(int cur,ll mask,int sum) {
	int i;
	if(sum>=mi) return;
	if(cur==N) {
		mi=sum;
		FOR(i,N) mip[i]=cup[i];
		return;
	}
	int tar=P[cur].second;
	if(mask) {
		for(i=58;i>0;i--) if(mask & (1LL<<i)) {
			mask ^= 1LL<<i;
			cup[tar]=i+1;
			if(abs(cup[tar]-A[tar])<abs(1-A[tar]))
				dfs(cur+1,mask & mat[i+1],sum+abs(cup[tar]-A[tar]));
		}
	}
	cup[tar]=1;
	dfs(cur+1,0,sum+abs(1-A[tar]));
}

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>N;
	mi=0;
	FOR(i,N) {
		cin>>A[i];
		P[i]=make_pair(A[i],i);
		mi+=A[i]-1;
		mip[i]=1;
	}
	for(x=1;x<=60;x++) for(y=1;y<=60;y++) if(__gcd(x,y)==1) mat[x] |= 1LL<<(y-1);
	sort(P,P+N);
	reverse(P,P+N);
	dfs(0,(1LL<<58)-1,0);
	FOR(i,N) _P("%d ",mip[i]);
	_P("\n");
}

まとめ

ちょっとTLEが怖くて、最初Submit後Resubmitした。
考えたら最大テストケースが自明なのでcustom invocationで試せばよかったな…。