POJ-3349: Snowflake Snow Snowflakes

keyword

ハッシュテーブル　C++

問題概要

N(<10^5)個のデータが与えられる。同じものがあるかどうか判定する問題。データは長さ6の配列で与えられ、reverse(), rotate()を使って一致するものは同じだと考える。

解法

前の記事にしたがってそのまま実装する。メモリ制限が64MBのとき確保できる32bitの配列のサイズは2^23が目安。安全を取って今回はサイズを2^22とした。このとき、特定のひとつのハッシュ値が衝突する確率はN/HASH_SIZEで、この値は1/40位。ちょっと大きくて気になるレベルだけど無視した(テストケースがよほど多くない限り基数を取り替えたら通るレベル)。実装時間16分。

感想

Eclipse+CDTを使って書いてみたけど微妙だ…。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef unsigned int uint;

const int HASH_SIZE = 1<<22;
const int MASK = HASH_SIZE - 1;
const uint P1 = 1000000007;
const uint P2 = 999999997;
uint hash_table[HASH_SIZE];

inline uint hash(vector<uint>& t, uint P){
	uint ret = 0, b = 1;
	for(int i=0; i<6; i++){
		ret += b*(uint)t[i];
		b *= P;
	}
	return ret;
}

inline vector<uint> getMin(vector<uint>& t){
	vector<uint> ret = t;
	for(int k=0; k<2; k++){
		for(int i=0; i<6; i++){
			rotate(t.begin(), t.begin()+1, t.end());
			if(ret > t){
				ret = t;
			}
		}
		reverse(t.begin(), t.end());
	}
	return ret;
}

int main(){
	int n;
	scanf("%d", &n);
	vector<uint> t(6);
	for(int i=0; i<n; i++){
		for(int j=0; j<6; j++){
			scanf("%u", &t[j]);
		}
		t = getMin(t);
		uint hash1 = hash(t, P1)&MASK;
		uint hash2 = hash(t, P2);
		if(!hash2) hash2 = 1<<30;
		if(!hash_table[hash1]){
			hash_table[hash1] = hash2;
		}
		else if(hash_table[hash1] == hash2){
			return puts("Twin snowflakes found."), 0;
		}
	}
	return puts("No two snowflakes are alike."), 0;
}