ABC329 D問題 Election Quick Report

はじめに

自学の為、書いていきます。

解く問題

D - Election Quick Report

考えること

まず制約を見ます。N,M共に2*10^5の値を取る可能性があり、入力の度に都度全探索を行うといった解き方はできません。そこで、出力しなければならないものを今一度見ます。

出力しなければならないものは、
i票目開示時点での当選者
です。

次に、当選条件を見ます。
人Aiが当選する条件は、
1.獲得票数が最多かつ同じ票数の人物がいない
2.獲得票数が最多かつ同じ票数の人物がいる、しかし人Aiは番号が最小

です。ここである人Aiが当選する条件を考えます。j票目まで開示したときに人Aiが当選するケースとして以下のケースが考えられます。

1.人Aiはj-1票目時点で1位であった。j票目の票が誰かに入ってもそのまま1位であるケース。

2.人Aiはj-1票目時点で2位であった。j票目の票が人Aiに入り人Aiが1位に繰り上がるケース。

これを判別するために、「j番目の票が入った際の票数と入った人の番号」、「j-1票目時点で1位だった人物の票数と番号」が必要です。これはpair<int,int>で管理してしまえば楽です。

答え

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<long double,long double>;
using ull = unsigned long long;

int main()
{
int N,M;
cin >> N >> M;
vector<int> A(M);
for(int i=0;i<M;i++) cin >> A[i];

pair<int,int> temp={1000000,1000000};
vector<int> human(N+1);
for(int i=0;i<M;i++){
    human[A[i]]--;
    pair<int,int> now={A[i],human[A[i]]};
    if(now.second<temp.second){
        cout << A[i] << endl;
        temp=now;
    }else if(now.first<temp.first && now.second==temp.second){
        cout << A[i] << endl;
        temp=now;
    }else{
        cout << temp.first << endl;
    }
}

}

特筆すべき点として、1票目の人物は必ず当選するので、そのような条件を考えます。自分のプログラムでは、0票目の人物は番号10^6で得票数10^6としています。自分のプログラムの方針では、票数はマイナスで考えているため票数は必ず0以下になり、問題制約から人物の番号が10^6になることはないので、必ず１票目の人物が出力されます。

この解法ではなぜか、human[A[i]]--;のように票をマイナスで考えています。minを用いて問題を解こうとしたときの名残をそのまま残してしまっていますが、バグのもとになるのでやめた方が良いです。