TopCoder SRM621 DIV2 HARD - MixingColors

Source

TopCoder SRM621 DIV2 HARD (1000pt)
Problem Statement

問題概要

色は正の整数で表される.
色 $i$ と色 $j$ を混ぜると色 $i\ {\rm XOR}\ j$ が得られる(色 $i$ や色 $j$ は無くならない).
$N$ 色からなる欲しい色の集合 $\{C_k\}_{k=1}^N$ が与えられる.
好きな色が買えるとき,全ての欲しい色を手に入れるために最小限買わなくてはいけない色の数を求める問題.

解法

色は $2$ 進数で表して,${\mathbb Z}/2{\mathbb Z}$ 上のベクトルとみなす.
問題を言い換えると,$\{C_k\}$ の張る空間は何次元か?(基底に対応する色のみ買えば良い)ということなので,$C_k$ を並べて行列を作って,ガウスの消去法などでランクを求める.

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

#include<bits/stdc++.h>
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 ull unsigned ll
int binaryGaussJordan(int r, int c, int right, ull **mat){int i,j,k,b =(c+right+63)/64,a=0;rep(j,c){REP(i,a,r)if(mat[i][j>>6]&(1ULL<<(j&63))) break;if(i==r)continue;if(i!=a)REP(k,j>>6,b)swap(mat[i][k],mat[a][k]);REP(i,a+1,r)if(mat[i][j>>6]&(1ULL<<(j&63)))REP(k,j>>6,b)mat[i][k]^=mat[a][k];a++;}return a;}

class MixingColors {
public:
int minColors(vector <int> colors) {
  int i, j, k, n;
  int res;
  ull *mat[100];
  rep(i,100) mat[i] = (ull *)malloc(sizeof(ull));

  n = colors.size();
  rep(i,n) mat[i][0] = colors[i];
  res = binaryGaussJordan(n, 32, 0, mat);

  return res;
}

}

Current time: 2017年11月21日04時13分50秒
Last modified: 2014年05月24日04時42分48秒 (by laycrs)
Tags: Competitive_Programming TopCoder Single_Round_Match SRM621 SRM_Div2_Hard
トップページに戻る

Logged in as: unknown user (not login)

ログイン: