AtCoder Regular Contest #021 D問題 - だいたい最小全域木

Source

AtCoder Regular Contest #021
問題文

問題概要

$200$ 次元のベクトル $5000$ 本が乱数で作られる.ベクトルの各要素は $-50000$ 以上 $50000$ 以下で $0$ ではない.
各ベクトルをノードとみなして,全域木を作る.
エッジを張るコストは,張る $2$ ベクトルのコサイン類似度を $s$ として,$1-s$ だけコストがかかる.
最小全域木のコストの $1.01$ 倍以下の全域木を $1$ つ求める問題.

解法

各要素のうち,正負が一致している要素が $110$ 個以上のベクトル間の枝のみを考えてクラスカルすると通る.
正負はビットに押し込み,高速にビットの数を数えれば十分に間に合う.
他にもやりかたはあるかもしれない.

C++によるスパゲッティなソースコード

#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: 2017年07月23日17時39分11秒
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)

ログイン: