AtCoder Regular Contest #021
問題文
$200$ 次元のベクトル $5000$ 本が乱数で作られる.ベクトルの各要素は $-50000$ 以上 $50000$ 以下で $0$ ではない.
各ベクトルをノードとみなして,全域木を作る.
エッジを張るコストは,張る $2$ ベクトルのコサイン類似度を $s$ として,$1-s$ だけコストがかかる.
最小全域木のコストの $1.01$ 倍以下の全域木を $1$ つ求める問題.
各要素のうち,正負が一致している要素が $110$ 個以上のベクトル間の枝のみを考えてクラスカルすると通る.
正負はビットに押し込み,高速にビットの数を数えれば十分に間に合う.
他にもやりかたはあるかもしれない.
#include<cstdio>
#include<vector>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<string>
#include<utility>
#include<iostream>
#include<cmath>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define ll long long
#define mygc(c) (c)=getchar_unlocked()
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
double p[5100][210];
ll bt[5100][4];
void gen(int seed){
unsigned x = 123456789;
unsigned y = 362436069;
unsigned z = 521288629;
unsigned w = seed;
unsigned t;
int v;
int i, j;
rep(i,5000) rep(j,200){
t = x ^ (x << 11);
x = y;
y = z;
z = w;
w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
v = (int)(w % 100000) - 50000;
if(v >= 0) v++;
p[i][j] = v;
}
}
void unionInit(int d[],int s){int i;rep(i,s)d[i]=i;}
int unionGet(int d[],int n){int t=n,k;while(d[t]!=t)t=d[t];while(d[n]!=n)k=d[n],d[n]=t,n=k;return n;}
int unionConnect(int d[],int a,int b){a=unionGet(d,a);b=unionGet(d,b);if(a==b)return 0;d[a]=b;return 1;}
int ind[5100];
pair<double,pair<int,int> > edge[1500000];
template<class T>
int bitCountSlow(T n){
int res = 0;
while(n) res += n%2, n/=2;
return res;
}
template<class T>
int bitCount(T n){
int i, res = 0;
static int init = 0, bt[65536];
if(init==0){
init = 1;
rep(i,65536) bt[i] = bitCountSlow(i);
}
while(n) res += bt[n%65536], n /= 65536;
return res;
}
int main(){
int S;
int i, j, k, mm, x;
int n = 5000, m = 200;
double len;
double cost;
int ind[5100];
reader(&S);
gen(S);
rep(i,n){
len = 0;
rep(j,m) len += (double)p[i][j]*p[i][j];
len = sqrt(len);
rep(j,m) p[i][j] /= len;
}
rep(i,n){
rep(j,4) bt[i][j] = 0;
rep(j,m) if(p[i][j] > 0) bt[i][j/60] += (1LL<<(j%60));
}
mm = 0;
rep(i,n){
REP(j,i+1,n){
k = 200;
rep(x,4) k -= bitCount(bt[i][x]^bt[j][x]);
if(k < 110) continue;
cost = 1;
rep(x,m) cost -= p[i][x] * p[j][x];
edge[mm++] = make_pair(cost, make_pair(i,j));
}
}
cost = 0;
sort(edge, edge+mm);
unionInit(ind, n);
rep(k,mm){
i = edge[k].second.first;
j = edge[k].second.second;
if(unionConnect(ind,i,j)){
printf("%d %d\n",i+1,j+1);
cost += edge[k].first;
}
}
// printf("cost %.10f\n",cost);
return 0;
}
Current time: 2024年03月29日22時18分05秒
Last modified: 2014年04月13日02時46分30秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC021 ARC_D
トップページに戻る
Logged in as: unknown user (not login)