UVa-11286, POJ-3640 : Conformity

問題概要

N(<1000)人の生徒は100~499の数字を5つ選ぶ。最も多く選ばれた集合(タイの場合は全部)を選んだ生徒の数を答える問題。

解法

数字5個の集合はソートしてから500進数だと思えば64ビットに収まる。なのでmapで数を簡単に管理できる。

acceptされたコード

計算量O(N * log N)。

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

typedef long long int64;

int N;

int solve(){
	map<int64, int> dict;
	int maxi = 0;
	for(int i=0; i<N; i++){
		int xs[5];
		scanf("%d%d%d%d%d",xs, xs+1, xs+2, xs+3, xs+4);
		sort(xs, xs+5);
		int64 hash = 0;
		for(int j=0; j<5; j++){
			hash = hash * 500 + xs[j];
		}
		maxi = max(maxi, ++dict[hash]);
	}

	int ans = 0;
	for(map<int64, int>::iterator itr = dict.begin(); itr!=dict.end(); itr++){
		if(itr->second == maxi){
			ans += maxi;
		}
	}

	return ans;
}

int main(){
	while(scanf("%d", &N), N){
		printf("%d\n", solve());
	}

	return 0;
}