【AtCoder】ABC 483 C - Second Choice Election

C - Second Choice Electionatcoder.jp favicon

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 770 / NoviSteps: 1Q / 配点: 300 点

問題概要

ある村の村長候補者は NN 人おり、候補者 11, 候補者 22, …\ldots, 候補者 NN と番号づけられている。 投票者は MM 人おり、ii 人目の投票者の投票先の第一希望は候補者 AiA_i、第二希望は候補者 BiB_i である。

候補者のうち一人のみが辞退した時、それぞれの投票者は以下のように投票する。

  • 第一希望の候補者が辞退していなければ、第一希望の候補者に投票する。
  • 第一希望の候補者が辞退していれば、第二希望の候補者に投票する。

辞退していない候補者のうち、得票数が最大の候補者が当選する。 また、そのような候補者が複数いる場合は、番号が最小の候補者が当選する。

k=1,2,…,Nk=1,2,\ldots,N それぞれについて、候補者 kk のみが辞退した場合に当選する候補者の番号を求めよ。

制約

  • 2≤N≤2×1052 \leq N \leq 2\times 10^5
  • 1≤M≤2×1051 \leq M \leq 2\times 10^5
  • 1≤Ai,Bi≤N1 \leq A_i,B_i \leq N
  • Ai≠BiA_i\neq B_i
  • 入力はすべて整数

考察

やりたいことの大きな方針としては、第一希望の得票数を基準にして、辞退する候補者から第二希望へ移る票だけを更新することである。

そこで、cnti\mathrm{cnt}_i に候補者 ii の第一希望の得票数を格納し、候補者の番号 ii と共にsetに追加しておく。 ここで、比較関数は cnti\mathrm{cnt}_i の降順、それが同数なら ii の昇順に並べるものとする。

このとき、setの先頭にある要素が当選する候補者である。


さて、各候補者 kk が辞退した場合を考えると、得票数が変化するのは以下の候補者のみである。

  • 辞退した候補者 kk: 当選者対象から外れる。
  • 候補者 kk を第一希望としていた投票者の第二希望 BiB_i: 1票増える。

ここで、secondk\mathrm{second}_k に、候補者 kk を第一希望とする投票者の第二希望リストを格納しておくことで、候補者 kk が辞退した場合の得票数の変化を効率的に計算できる。

これを用いると、各 kk に対しては以下の処理を行えばよくなる。


  1. 候補者 kk の要素 (cntk,k)(\mathrm{cnt}_k, k) をsetから削除する。
  2. secondk\mathrm{second}_k の各要素 xx に対して、候補者 xx の要素 (cntx,x)(\mathrm{cnt}_x, x) をsetから削除し、cntx\mathrm{cnt}_x を 1 増やして再度setに追加する。
  3. setの先頭にある要素の候補者番号を出力する。
  4. secondk\mathrm{second}_k の各要素 xx に対して、候補者 xx の要素 (cntx,x)(\mathrm{cnt}_x, x) をsetから削除し、cntx\mathrm{cnt}_x を 1 減らして再度setに追加する。
  5. 候補者 kk の要素 (cntk,k)(\mathrm{cnt}_k, k) をsetに追加する。

答えを出力した後は、元の状態に戻すことを忘れないこと。


候補者 kk の処理では、secondk\mathrm{second}_k の要素数を dkd_k とすると、O((dk+1)log⁡N)O((d_k+1)\log N) の計算量がかかるので、全体の計算量は O((N+M)log⁡N)O((N+M)\log N) である。

実装例

CPP
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.}
atcoder.jp favicon

実装時間: 25分

コメント

C問題にしてはとっつきにくい問題で難しかった。