ABC483 C - Second Choice Election
- サイト
- AtCoder
- コンテスト
- ABC483
- 問題
- C - Second Choice Election
- 難易度
- 770
候補者が 人、投票者が 人いて、投票者 の第一希望は 、第二希望は です。候補者が 人辞退すると、その候補者を第一希望としていた人だけが第二希望に投票します。
各候補者が辞退した場合について、得票数が最大の候補者を求める問題です。同票なら番号が最小の候補者を選びます()。
まず、全員が第一希望に投票したときの得票数を数えます。また、候補者 を第一希望としている人の第二希望を tmp[i] にまとめます。
候補者 が辞退するとき、移動するのは tmp[i] に対応する票だけです。それぞれについて の得票数を 減らし、第二希望の候補者の得票数を 増やします。この状態で当選者を求めたら、移動した票を元に戻します。
得票数の更新と当選者の取得には、候補者ごとの得票数に加え、「得票数の降順、同票なら番号の昇順」に並べた集合を管理すればよいです。更新時に古い組を削除して新しい組を追加すると、集合の先頭が当選者になります。
辞退した候補者の得票数は になります。 なので必ず誰かが 票以上を得ており、辞退した候補者が選ばれることはありません。得票数が の候補者を集合に入れなくても答えは変わりません。
各票は、その第一希望の候補者が辞退するときにだけ移動し、その後復元されます。全体で 回の更新を行うので、計算量は です。
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 始まりにしています。