数の制限は小さいが結構時間を食う問題。
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で試せばよかったな…。