問題設定がちょっとややこしいね。
https://yukicoder.me/problems/no/937
問題
整数列Aが与えられる。
ここに対し、以下の処理を任意に繰り返す。
- 異なる値を2つx,yと選び、x xor yを追加する
- 値を1つ選び、2倍の値を追加する
- 自身が追加した要素を消す
1回だけど、A中である要素を選択し、その倍数の値を持つ要素を、全てその値で割ることができるとする。
その後の値の総和の最小値を求めよ。
解法
自身で生成した値は消せるので、最終的にどの値が生成可能か、というのを列挙し、あとはすべての値で実際に割ってみることにする。
あとはこの処理でどんな値を生成できるかだが、2進数において加算の代わりにxorを取った場合のAのGCDとその倍数が候補になる。
GCDはGF2上の掃出し法と同様に求めることができる。
以下のコードでは、倍数もGCDを1~2^17倍したものを実際に総当たりしている。
int N; int A[101010]; int C[101010]; ll ret[101010]; int GCD(int x,int y) { if(x<y) swap(x,y); if(y==0) return x; int z=y; while(__builtin_clz(x)!=__builtin_clz(z)) z<<=1; return GCD(y,x^z); } void solve() { int i,j,k,l,r,x,y; string s; cin>>N; ll sum=0; int g=0; FOR(i,N) { cin>>A[i]; g=GCD(g,A[i]); C[A[i]]++; sum+=A[i]; } ll mi=1LL<<60; for(i=1;i<=100000;i++) { ret[i]=sum; for(j=i;j<=100000;j+=i) { ret[i]-=1LL*C[j]*j; ret[i]+=1LL*C[j]*(j/i); } if(i%g==0) mi=min(mi,ret[i]); } for(int m=1;m<1<<17;m++) { ll t=0; FOR(i,17) if(m&(1<<i)) t^=(ll)g<<i; if(t<=100000) mi=min(mi,ret[t]); } cout<<mi<<endl; }
まとめ
単にbit vectorを考えるだけでなく、GCDを考えるのは珍しいな。