第21回国会議員選挙

区分アルゴリズム:実装

質問する

各政党が地域区の議席数と比例代表の得票結果をそれぞれ提示した場合、各政党が第21回国会議員選挙の結果に基づいて獲得した総議席数を算出する.議員総数は300人、地域救国会議員は253人、比例代表国会議員は47人.
比例代表議席は比例代表総選挙で有効投票総数3%以上または地域救国会議員選挙で5議席以上を獲得した政党(封鎖条項)にのみ割り当てられる.比例代表議席を配分する政党を議席配分政党と呼ぶ.第21代国会議員選挙について比例代表の議席配分方式は以下の通り.




入力
1行目は選挙候補の政党数Pと総投票者数Vである.(1 <= P <= 50), (1 <= V <= 10^9)
次のP行は各政党の政党名と地域議席数を示し、比例代表の国会議員選挙の得票数を示した.正名は最大50文字の小文字と逆数()で構成され、重複しません.
地域区の議席数の和は253議席を超えず、比例代表の国会議員選挙の票数の和はVを超えない.
しゅつりょく
各政党が第21代国会で獲得した議席数に基づき、議席数降順に並び、政党名とともに出力する.議席数が同じなら、まず政党名優先の政党を輸出する.
入力例1
5 24430476
redshift 105 7960272
deobureo_minkyu_party 110 6069744
i_might_be_accepted 25 6355572
justice_hui 2 1719891
god_fan 0 626853
サンプル出力1
deobureo_minkyu_party 115
redshift 111
i_might_be_accepted 52
justice_hui 11
god_fan 0
今回の選挙では、5つの政党と24430476人の有権者が投票した.これに基づいて以下のように計算する.

比例得票率は無効票(1698144票)を除く.god fan政党の得票率は3%に満たず、地域区の議席も5議席に満たないため、比例代表の議席は得られない.
(一段階)30議席に対し、全国単位準連動(連動比率50%)方式で各政党連動配分議席数を算出

(2-2段階)各政党連動配分議席数の和>30議席(各政党連動配分議席は守衛率で配分)

(第3段階)17席に対して既存席配分方式(並立型)で配分

最終議席数

ノート
2020年1月14日に施行される公職選挙法(法律第168664号)を基準としている.ただし、以下の例外が適用されます.
小数点以下の数が大きい順に議席を割り当てる場合、小数点以下の数が全く同じであれば、まず符号の小さい政党に割り当てる.△この場合、選挙法は抽選で決まる.
少なくとも1つの政党以上.
(s i^\prime>0).

問題を解く

問題の形式によって実施すればよい.ただし、例題のように、答えを確認しながら実施し、問題に制限のない条件であっても、自分が制限する愚かな考えに注意しなければならない.サンプル出力を比較すると、問題に存在しない条件-小数点4位で、私はずっと四捨五入を行っていた.この問題で、70%の人が「間違っている」と判定されたからだ.

ソースコード

#include <bits/stdc++.h>

using namespace std;

int p, v, rv, n, r; 
struct node {
	string name;
    int ri, vote, total;
    double rate, prop_rate, p1, p2, p3, p2_rate, p3_rate;
    bool prop_able;
};
vector<node> party;
bool compare1(const pair<int, double> &a, const pair<int, double> &b); // 소수점 내림차순 정렬
bool compare2(const node &a, const node &b); // 전체 의석 수 내림차순 정렬
void zero(); // 득표율, 비례득표율 계산
void first(); // 1단계
void second(); // 2단계
void third(); // 3단계
void solve(); // Output 출력

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> p >> v;
	rv = v;
	for(int i = 0; i < p; i++) {
		node temp;
		cin >> temp.name >> temp.ri >> temp.vote;
		party.push_back(temp);
		rv -= temp.vote;
	}
	rv = v - rv; //유효표
	
	zero();
	first();
	second();
	third();
	solve();
	
	return 0;
}

bool compare1(const pair<int, double> &a, const pair<int, double> &b) {
	return a.second > b.second;
}

bool compare2(const node &a, const node &b) {
	if(a.total == b.total) {
		return a.name < b.name;
	}
	else {
		return a.total > b.total;
	}
}

void zero() {
	// 득표율 계산 + 비례대표의석 가질 수 있는지 계산 + 비례득표율용 유효 투표 수 계산
	for(int i = 0; i < p; i++) {
		party[i].rate = (1.0 * party[i].vote) / rv;
		//party[i].rate = round(party[i].rate * 10000) / 10000;
		
		if(party[i].ri >= 5 || party[i].rate >= 0.03) {
			party[i].prop_able = true;
		}
		else {
			party[i].prop_able = false;
			rv -= party[i].vote;
		}
	}
	
	// 비례득표율 계산
	for(int i = 0; i < p; i++) {
		if(party[i].prop_able) {
			party[i].prop_rate = (1.0 * party[i].vote) / rv;
			//party[i].prop_rate = round(party[i].prop_rate * 10000) / 10000;
		}
	}
}

void first() {
	n = 300;
	r = 253;
	// 1단계 변수 R 계산
	for(int i = 0; i < p; i++) {
		if(party[i].prop_able) {
			r -= party[i].ri;
		}
	}
	
	// 30석에 대한 각 정당별 연동배분의석수 산정
	for(int i = 0; i < p; i++) {
		if(party[i].prop_able) {
			party[i].p1 = ((n -r) * (1.0 * party[i].prop_rate) - party[i].ri) / 2;
			if(party[i].p1 < 1) {
				party[i].p1 = 0;
			}
			else {
				party[i].p1 = round(party[i].p1);
			}
		}
	}
	
}

void second() {
	int sum = 0; // 정당별 연동배분의석수 합계 구하는 변수
	int nSum = 0; // 정다별 연동배분의석수가 30석이 되도록 하는 변수
	vector<pair<int, double>> v;
	
	// 연동 배분 의석 수 합 구하기
	for(int i = 0; i < p; i++) {
		if(party[i].prop_able) {
			sum += party[i].p1;
		}
	}
	
	if(sum == 30) {
		for(int i = 0; i < p; i++ ) {
			party[i].p2 = party[i].p1;
		}
		return;
	}
	else if(sum < 30) {
		// 2-1단계 구현
		for(int i = 0; i < p; i++) {
			if(party[i].prop_able) {
				party[i].p2_rate = party[i].p1 + (30 - sum) * (1.0 * party[i].prop_rate);
				party[i].p2 = floor(party[i].p2_rate);
				party[i].p2_rate -= party[i].p2;
				
				nSum += party[i].p2;
				v.push_back({i, party[i].p2_rate});
			}
		}
		
		sort(v.begin(), v.end(), compare1);
		for(int i = 0; i < v.size(); i++) {
			if(nSum >= 30) {
				break;
			}
			party[v[i].first].p2++;
			nSum++;
		}
	}
	else if(sum > 30) {
		// 2-2단계 구현
		for(int i = 0; i < p; i++) {
			if(party[i].prop_able) {
				party[i].p2_rate = 30 * (1.0 * party[i].p1) / sum;
				party[i].p2 = floor(party[i].p2_rate);
				party[i].p2_rate -= party[i].p2;
				
				nSum += party[i].p2;
				v.push_back({i, party[i].p2_rate});
			}
		}
		
		sort(v.begin(), v.end(), compare1);
		for(int i = 0; i < v.size(); i++) {
			if(nSum >= 30) {
				break;
			}
			party[v[i].first].p2++;
			nSum++;
		}
	}
}

void third() {
	int sum = 0;
	vector<pair<int, double>> v;
	
	for(int i = 0; i < p; i++) {
		if(party[i].prop_able) {
			party[i].p3_rate = 17 * (1.0 * party[i].prop_rate);
			party[i].p3 = floor(party[i].p3_rate);
			party[i].p3_rate -= party[i].p3;
			
			sum += party[i].p3;
			v.push_back({i, party[i].p3_rate});
		}
	}
	
	sort(v.begin(), v.end(), compare1);
	for(int i = 0; i < v.size(); i++) {
		if(sum >= 17) {
			break;
		}
		party[v[i].first].p3++;
		sum++;
	}
}

void solve() {
	for(int i = 0; i < p; i++) {
		if(party[i].prop_able) {
			party[i].total = party[i].ri + party[i].p2 + party[i].p3;
		}
		else {
			party[i].total = party[i].ri;
		}
	}
	
	sort(party.begin(), party.end(), compare2);
	for(int i = 0; i < p; i++) {
		cout << party[i].name << " " << party[i].total << endl;
	}
}

題出所:https://www.acmicpc.net/problem/188912

カイドウ草が白駿で「そうだ!!」判定を受けた