コンテンツにスキップ

ABC483 C - Second Choice Election

サイト
AtCoder
コンテスト
ABC483
問題
C - Second Choice Election
難易度
770

候補者が NN 人、投票者が MM 人いて、投票者 ii の第一希望は AiA_i、第二希望は BiB_i です。候補者が 11 人辞退すると、その候補者を第一希望としていた人だけが第二希望に投票します。

各候補者が辞退した場合について、得票数が最大の候補者を求める問題です。同票なら番号が最小の候補者を選びます(N,M≤2×105N, M \le 2 \times 10^5)。

まず、全員が第一希望に投票したときの得票数を数えます。また、候補者 ii を第一希望としている人の第二希望を tmp[i] にまとめます。

候補者 ii が辞退するとき、移動するのは tmp[i] に対応する票だけです。それぞれについて ii の得票数を 11 減らし、第二希望の候補者の得票数を 11 増やします。この状態で当選者を求めたら、移動した票を元に戻します。

得票数の更新と当選者の取得には、候補者ごとの得票数に加え、「得票数の降順、同票なら番号の昇順」に並べた集合を管理すればよいです。更新時に古い組を削除して新しい組を追加すると、集合の先頭が当選者になります。

辞退した候補者の得票数は 00 になります。M≥1M \ge 1 なので必ず誰かが 11 票以上を得ており、辞退した候補者が選ばれることはありません。得票数が 00 の候補者を集合に入れなくても答えは変わりません。

各票は、その第一希望の候補者が辞退するときにだけ移動し、その後復元されます。全体で O(M)O(M) 回の更新を行うので、計算量は O(N+Mlog⁡N)O(N + M \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/counter.hpp"
void solve() {
LL(N, M);
VAL(AB, M, 2);
vvl tmp(N);
Counter<ll> cnt;
for (auto &[a, b] : AB) {
a--, b--;
tmp[a].push_back(b);
cnt.inc(a);
}
rep(i, N) {
for (ll j : tmp[i]) {
cnt.dec(i);
cnt.inc(j);
}
print(cnt.mode()->value + 1);
for (ll j : tmp[i]) {
cnt.dec(j);
cnt.inc(i);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

実装では、自作ライブラリの Counter を使っています。inc・dec で票を増減でき、mode() は個数が最大の値を、同数なら最小の値を返すので、当選者をそのまま求められます。候補者番号は内部では 0 始まりにしています。