CodeChef-AMBIDEX :Ambidextrous Chefs

問題概要

グラフの交わらない辺被覆(小さいほど良い)が最大いくつ作れるか求める問題。

解法

グラフだと気づかずに適当にgreedyしたけど割と良いスコアが出た。

acceptされたコード

#include <cstdio>
#include <ctime>
#include <cstring>
#include <algorithm>
#include <cassert>
#include <numeric>
using namespace std;

const double TOTAL_TIME_LIMIT = 3.0;
const int MAX_T = 10;
const int MAX_N = 100;
const int MAX_M = 1000;
const int INF = 1<<29;
const double DOUBLE_INF = 1e100;

void init(const int);
double solve(double);

int Ns[MAX_T], Ms[MAX_T], T;
double assigned_time[MAX_T];
int inp[MAX_T][MAX_M][2];
pair<int,pair<int,int> > input[MAX_M];
int perm[MAX_M];
int final_ans[MAX_M], ans[MAX_M];

int N, M;
int as[MAX_M][2];
int ts[MAX_M], tmp_ts[MAX_M], best_ts[MAX_M];
bool fs[MAX_N + 1];
int over[MAX_N + 1], tmp_over[MAX_N + 1], best_over[MAX_N + 1];
int appear[MAX_N + 1], tmp_appear[MAX_N + 1];
int order[MAX_M];
bool checked[MAX_N][MAX_N];
bool filled[MAX_N];


void read_input(){
	scanf("%d", &T);
	for(int i=0; i<T; i++){
		scanf("%d%d", Ns+i, Ms+i);
		for(int k=0; k<2; k++){
			for(int j=0; j<Ms[i]; j++){
				scanf("%d", inp[i][j]+k);
			}
		}
	}
}


void handle(){

	//適当に割り振り
	for(int i=0; i<T; i++){
		assigned_time[i] = TOTAL_TIME_LIMIT / T;
	}

	for(int i=0; i<T; i++){
		memset(final_ans, 0, sizeof(final_ans));
		double best_score = 0.0;
		for(int k=0; k<1; k++){
			init(i);
			double score = solve(assigned_time[i]);
			if(best_score < score){
				best_score = score;
				for(int j=0; j<M; j++){
					final_ans[j] = ans[perm[j]];
				}
			}
		}
		//printf("score:%f\n", best_score);
		for(int j=0; j<M; j++){
			printf("%d%c", final_ans[j], j==M-1?'\n':' ');
		}
	}

}



void init(const int idx){
	N = Ns[idx];
	M = Ms[idx];
	for(int i=0; i<M; i++){
		input[i] = make_pair(i, make_pair(inp[idx][i][0], inp[idx][i][1]));
	}
	random_shuffle(input, input + M);

	for(int i=0; i<M; i++){
		perm[input[i].first] = i;
	}

	for(int i=0; i<M; i++){
		as[i][0] = input[i].second.first;
		as[i][1] = input[i].second.second;
	}

}

double sq(double x){
	return x * x;
}

double search2(const int team_id){
	memset(fs, false, sizeof(fs));
	int f_cnt = 0;

	random_shuffle(order, order + M);

	for(int k=0; ;k++){

		int key = -1, best_new = 0, mini_penalty = 0;
		for(int ii=0; ii<M; ii++)if(ts[order[ii]] == 0){
			int i = order[ii];
			int cnt = 0, penalty = 0;
			for(int j=0; j<2; j++){
				if(!fs[as[i][j]]){
					cnt++;
				}
			}
			if(cnt == 2){
				//penalty -= over[as[i][0]] + over[as[i][1]];
				penalty = -max(over[as[i][0]], over[as[i][1]]);
			}
			else if(cnt == 1){
				if(!fs[as[i][0]]){
					penalty += over[as[i][1]];
				}
				else{
					penalty += over[as[i][0]];
				}
			}
			if(best_new < cnt || (best_new == cnt && penalty < mini_penalty)){
				key = i;
				best_new = cnt;
				mini_penalty = penalty;
			}
		}

		if(key == -1){
			break;
		}
		else{
			f_cnt += best_new;
			ts[key] = -team_id;
			for(int j=0; j<2; j++){
				if(!fs[as[key][j]]){
					fs[as[key][j]] = true;
				}
				else{
					over[as[key][j]]++;
				}
			}
		}
		if(f_cnt == N){
			/*
			memset(tmp_appear, 0, sizeof(tmp_appear));
			for(int i=0; i<M; i++)if(ts[i] == 0){
				for(int j=0; j<2; j++){
					tmp_appear[as[i][j]]++;
				}
			}
			int mini = *min_element(tmp_appear + 1, tmp_appear + N + 1);
			*/
			int maxi = *max_element(over + 1, over + N + 1);
			double pen = 0.0;
			for(int i=1; i<=N; i++){
				pen += sq(over[i]);
			}
			return k*1e12 + maxi*1e7 + pen;
		}

	}

	return DOUBLE_INF;
}

double search(const int team_id){
	memset(fs, false, sizeof(fs));
	int f_cnt = 0;

	random_shuffle(order, order + M);

	for(int k=0; ; k++){

		int key = -1, best_new = 0, mini_penalty = 0;
		for(int ii=0; ii<M; ii++)if(ts[order[ii]] == 0){
			int i = order[ii];
			int cnt = 0, penalty = 0;
			for(int j=0; j<2; j++){
				if(!fs[as[i][j]]){
					cnt++;
				}
				else{
					penalty += over[as[i][j]];
				}
			}
			if(cnt == 2){
				k++;
				ts[i] = -team_id;
				f_cnt += 2;
				for(int j=0; j<2; j++){
					fs[as[i][j]] = true;
				}
			}
			if(best_new < cnt || (best_new == cnt && penalty < mini_penalty)){
				key = i;
				best_new = cnt;
				mini_penalty = penalty;
			}
		}

		if(key == -1){
			break;
		}
		else if(best_new == 1){
			f_cnt += best_new;
			ts[key] = -team_id;
			for(int j=0; j<2; j++){
				if(!fs[as[key][j]]){
					fs[as[key][j]] = true;
				}
				else{
					over[as[key][j]]++;
				}
			}
		}
		if(f_cnt == N){
			/*
			memset(tmp_appear, 0, sizeof(tmp_appear));
			for(int i=0; i<M; i++)if(ts[i] == 0){
				for(int j=0; j<2; j++){
					tmp_appear[as[i][j]]++;
				}
			}
			int mini = *min_element(tmp_appear + 1, tmp_appear + N + 1);
			*/
			int maxi = *max_element(over + 1, over + N + 1);
			double pen = 0.0;
			for(int i=1; i<=N; i++){
				pen += sq(over[i]);
			}
			return k*1e12 + maxi*1e7 + pen;
		}

	}

	return DOUBLE_INF;
}


double solve(const double time_limit){
	int team_id = 1, f_cnt = 0;

	memset(ts, 0, sizeof(ts));
	memset(fs, false, sizeof(fs));
	memset(over, 0, sizeof(over));
	memset(appear, 0, sizeof(appear));

	for(int i=0; i<M; i++){
		order[i] = M - 1 - i;
		for(int j=0; j<2; j++){
			appear[as[i][j]]++;
		}
	}

	int max_appear = *max_element(appear+1, appear + N+1);
	for(int i=1; i<=N; i++){
		over[i] = max_appear - appear[i];
	}

	for(;;){
		double mini_penalty = DOUBLE_INF;
		memcpy(tmp_ts, ts, sizeof(ts));
		memcpy(tmp_over, over, sizeof(over));
		for(int k=0; k<500/T; k++){
			double penalty = search(team_id);
			if(penalty == DOUBLE_INF){
				break;
			}
			else if(penalty < mini_penalty){
				mini_penalty = penalty;
				memcpy(best_ts, ts, sizeof(ts));
				memcpy(best_over, over, sizeof(over));
			}
			memcpy(ts, tmp_ts, sizeof(ts));
			memcpy(over, tmp_over, sizeof(over));
		}

		memcpy(ts, best_ts, sizeof(ts));
		memcpy(over, best_over, sizeof(over));

		if(mini_penalty == DOUBLE_INF){
			break;
		}

		team_id++;
	}


	for(int i=0; i<M; i++){
		ans[i] = (ts[i] != 0 && -ts[i] < team_id ? -ts[i] : 0);
	}

	return (double)(N*(team_id - 1) - (M - count(ans, ans+M, 0))) / M;
}


int main(){

	read_input();
	handle();

	return 0;
}