【AtCoder】ABC 483 C - Second Choice Election

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 770 / NoviSteps: 1Q / 配点: 300 点
問題概要
ある村の村長候補者は 人おり、候補者 , 候補者 , , 候補者 と番号づけられている。 投票者は 人おり、 人目の投票者の投票先の第一希望は候補者 、第二希望は候補者 である。
候補者のうち一人のみが辞退した時、それぞれの投票者は以下のように投票する。
- 第一希望の候補者が辞退していなければ、第一希望の候補者に投票する。
- 第一希望の候補者が辞退していれば、第二希望の候補者に投票する。
辞退していない候補者のうち、得票数が最大の候補者が当選する。 また、そのような候補者が複数いる場合は、番号が最小の候補者が当選する。
それぞれについて、候補者 のみが辞退した場合に当選する候補者の番号を求めよ。
制約
- 入力はすべて整数
考察
やりたいことの大きな方針としては、第一希望の得票数を基準にして、辞退する候補者から第二希望へ移る票だけを更新することである。
そこで、 に候補者 の第一希望の得票数を格納し、候補者の番号 と共にsetに追加しておく。
ここで、比較関数は の降順、それが同数なら の昇順に並べるものとする。
このとき、setの先頭にある要素が当選する候補者である。
さて、各候補者 が辞退した場合を考えると、得票数が変化するのは以下の候補者のみである。
- 辞退した候補者 : 当選者対象から外れる。
- 候補者 を第一希望としていた投票者の第二希望 : 1票増える。
ここで、 に、候補者 を第一希望とする投票者の第二希望リストを格納しておくことで、候補者 が辞退した場合の得票数の変化を効率的に計算できる。
これを用いると、各 に対しては以下の処理を行えばよくなる。
- 候補者 の要素 を
setから削除する。 - の各要素 に対して、候補者 の要素 を
setから削除し、 を 1 増やして再度setに追加する。 setの先頭にある要素の候補者番号を出力する。- の各要素 に対して、候補者 の要素 を
setから削除し、 を 1 減らして再度setに追加する。 - 候補者 の要素 を
setに追加する。
答えを出力した後は、元の状態に戻すことを忘れないこと。
候補者 の処理では、 の要素数を とすると、 の計算量がかかるので、全体の計算量は である。
実装例
1.#include <bits/stdc++.h>2.using namespace std;3. 4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)5. 6.using Pair_int = pair<int, int>;7. 8.// ======================================== //9. 10.struct Comp {11. bool operator()(const Pair_int& a, const Pair_int& b) const {12. if (a.first != b.first) {13. return a.first > b.first;14. }15. return a.second < b.second;16. }17.};18. 19.int main()20.{21. int N, M;22. cin >> N >> M;23. vector<int> cnt(N, 0);24. vector<vector<int>> second(N);25. rep(i, 0, M) {26. int A, B;27. cin >> A >> B;28. A--, B--;29. 30. cnt[A]++;31. second[A].push_back(B);32. }33. 34. set<Pair_int, Comp> st;35. rep(i, 0, N) {36. st.insert({ cnt[i], i });37. }38. 39. rep(k, 0, N) {40. st.erase({ cnt[k], k });41. 42. for (auto x : second[k]) {43. st.erase({ cnt[x], x });44. cnt[x]++;45. st.insert({ cnt[x], x });46. }47. 48. cout << st.begin()->second + 1 << endl;49. 50. for (auto x : second[k]) {51. st.erase({ cnt[x], x });52. cnt[x]--;53. st.insert({ cnt[x], x });54. }55. 56. st.insert({ cnt[k], k });57. }58. 59. return 0;60.}実装時間: 25分
コメント
C問題にしてはとっつきにくい問題で難しかった。





