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; }