[백준][C++] 18891: 제21대 국회의원 선거

문제 링크: https://www.acmicpc.net/problem/18891

 

아... 정말 끔찍한 문제였습니다.

문제가 끔찍하다기 보단 준연동형 비례대표제가 얼마나 개판이었는지 보여준다고 해야겠네요.

 

문제 푼지 몇 달 지나서 기억은 잘 안나는데.. 문제만 몇 번을 반복해서 읽었습니다.

주의해야할 점이 뭐 여러개 있겠지만 실수연산에 주의를 기울여야 합니다. 비례대표 47석 중 30석으로 조정하는 작업이 좀 까다롭네요. 17석 배분할 때 소수점 이하 수가 큰 순서대로 배분하는데 이거 또한 주의를 하셔야 합니다.

#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;

const int N = 300;	// 국회의원 정원


//정당
struct party {
	int idx;	//기호
	string name;	//정당명
	bool is_blocked;	//봉쇄조항 (득표 3% 미만, 지역구 5석 미만 => true)
	
	int regional;	//지역구 의석수
	int prop;		//비례대표 의석수
	int prop_votes;	//비례대표 득표수
	double prop_percentage;	// 비례득표율 (의석할당정당 대상)
};

// 30석 맞추기
void matching(vector<int>& arr, vector<pair<double, int>>& pts, int total) {
	int curr = 0;
	for (auto& p : arr)
		curr += p;

	if (curr < total) {
		sort(pts.begin(), pts.end(), [](auto& a, auto& b) {
			return a.first > b.first;
		});

		for (int i = 0; i < pts.size(); ++i) {
			++arr[pts[i].second];
			++curr;

			if (curr == total) break;
		}
	}
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);


	int p, v;
	cin >> p >> v;
	vector<party> parties(p);

	int R = 253;			//무소속 지역구 당선인 + 의석할당정당 아닌 정당의 지역구 당선인
	int total_votes = 0;	// 무효표 뺀 비례표 총합
	int idx = 0;			// 정당 기호

	for (auto& p : parties) {
		cin >> p.name >> p.regional >> p.prop_votes;
		p.idx = ++idx;
		R -= p.regional;
		total_votes += p.prop_votes;
	}

	// 비례대표 득표비율 계산 (봉쇄조항)
	int total_votes_valid = total_votes;	// 의석할당정당이 받은 총 표수
	for (auto& p : parties) {
		// 지역구 5석미만 && 비례투표총수 3%미만 득표
		if (p.regional < 5 && ((double)p.prop_votes / total_votes) < 0.03) {
			p.is_blocked = true;
			total_votes_valid -= p.prop_votes;
			R += p.regional;
		}
	}
	for (auto& p : parties) {
		if (!p.is_blocked) {
			p.prop_percentage = (double)p.prop_votes / total_votes_valid;
		}
	}

	////////////////////////////////////////////////////////////////////////////////////
	// 1. 배분
	////////////////////////////////////////////////////////////////////////////////////
	int allocated = 0;	// 현재까지 배분된 비례대표 의석수
	vector<int> s;
	for (auto& p : parties) {
		if (p.is_blocked) {
			s.push_back(0);
			continue;
		}

		double pt = ((N - R) * p.prop_percentage - p.regional) / 2.0;
		if (pt < 1) s.push_back(0);
		else s.push_back(round(pt));

		allocated += s.back();
	}

	// 2. 30석으로 맞추기
	if (allocated != 30) {
		vector<pair<double, int>> pts;
		for (int i = 0; i < parties.size(); ++i) {
			auto& p = parties[i];
			if (p.is_blocked) continue;

			double pt;
			if (allocated < 30)
				pt = s[i] + (30 - allocated) * p.prop_percentage;
			else
				pt = 30.0 * s[i] / allocated;

			pts.emplace_back(pt - floor(pt), i);
			s[i] = floor(pt);
		}
		matching(s, pts, 30);
	}



	// 3. 나머지 17석 분배
	vector<int> t;
	vector<pair<double, int>> pts;
	for (int i = 0; i < parties.size(); ++i) {
		auto& p = parties[i];
		if (p.is_blocked) {
			t.push_back(0);
			continue;
		}

		double pt = 17.0 * p.prop_percentage;
		pts.emplace_back(pt - floor(pt), i);
		t.push_back(floor(pt));
	}
	matching(t, pts, 17);

	for (int i = 0; i < parties.size(); ++i) {
		auto& p = parties[i];
		p.prop = s[i] + t[i];
	}


	//1. 의석수 2. 정당명순 정렬
	sort(parties.begin(), parties.end(), [](const party& p1, const party& p2) {
		int chair1 = p1.regional + p1.prop, chair2 = p2.regional + p2.prop;
		if (chair1 == chair2)
			return p1.name < p2.name;
		return chair1 > chair2;
	});

	// 출력
	for (auto& p : parties) {
		cout << p.name << ' ' << p.regional + p.prop << '\n';
	}

	return 0;
}