C++で実装するオンライン選挙：TopVotedCandidateクラスの作り方と解法

問題概要

ある選挙では、i 番目の票が時刻 times[i] に候補者 persons[i] へ投じられたものとします。ここで、次のようなクエリ関数 TopVotedCandidate.q(int t) を実装することが求められます。この関数は、時刻 t の時点で選挙をリードしていた人物の番号を返します。時刻 t ちょうどに投じられた票もクエリの結果に含まれます。また、同点の場合は、同数の票を持つ候補者のうち最も新しい票を獲得した候補者が勝者となります。

例えば、TopVotedCandidate([0,1,1,0,0,1,0], [0,5,10,15,20,25,30]) で初期化し、q(3)、q(12)、q(25)、q(15)、q(24)、q(8) の順に呼び出すと、結果はそれぞれ [0, 1, 1, 0, 0, 1] となります。

その理由は以下の通りです。

• 時刻 3： 投票は [0] のみのため、候補者 0 がリードしています。
• 時刻 12： 投票は [0,1,1] となり、候補者 1 がリードしています。
• 時刻 25： 投票は [0,1,1,0,0,1] となり、候補者 1 がリードしています（同点の場合は最新の票が優先されるため）。

以降も同様に、時刻 15、24、そして 8 に対するクエリが続きます。

アルゴリズムの手順

この問題を解くために、以下の手順に従います。

1. 2つのマップ m と count を用意します。
2. コンストラクタ（初期化処理）で以下の作業を行います。
   • lead を -1 で初期化します。
   • i を 0 から times 配列のサイズまで繰り返します。
     • x := times[i]
     • count[persons[i]] を 1 増やします。
     • count[lead] <= count[persons[i]] であれば lead := persons[i] と更新し、m[x] := lead を設定します。それ以外の場合も m[x] := lead を設定します。
3. q() メソッドは次のように実装します。
   • m 内で t より大きい最初のキーの一つ前（upper_bound を 1 つ戻した位置）の要素を取得し、その値を返します。

ポイント解説

このアルゴリズムの鍵は、前計算の段階で「各投票時刻におけるリーダー」をマップ m に記録しておくことです。これにより、q(t) のクエリには「t 以下で最大の投票時刻」を探すだけで答えられるようになります。

std::map は内部が平衡二分探索木（赤黒木）で実装されているため、upper_bound による検索は O(log n) で完了します。前計算に O(n log n)、各クエリに O(log n) の計算量しかかからないため、同じデータセットに対して何度もクエリが発行されるような場面でも高速に動作します。

また、「同点の場合は最新の票が勝つ」という条件は、比較に使用している不等号 count[lead] <= count[persons[i]] によって自然に実現されています。新しい候補者の票数が現リーダーと並んだ瞬間にリーダーが交代する仕組みになっているのです。

C++ 実装例

#include <bits/stdc++.h>
using namespace std;
class TopVotedCandidate {
    public:
    map <int, int> m;
    map <int, int> count;
    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        int lead = -1;
        for(int i = 0; i < times.size(); i++){
            int x = times[i];
            count[persons[i]]++;
            if(count[lead] <= count[persons[i]]){
                lead = persons[i];
                m[x] = lead;
            }else{
                m[x] = lead;
            }
        }
    }
    int q(int t) {
        return ((--m.upper_bound(t)) -> second);
    }
};
main(){
    vector<int> v1 = {0,1,1,0,0,1,0}, v2 = {0,5,10,15,20,25,30};
    TopVotedCandidate ob(v1, v2);
    cout << (ob.q(3)) << endl;
    cout << (ob.q(12)) << endl;
    cout << (ob.q(25)) << endl;
    cout << (ob.q(15)) << endl;
    cout << (ob.q(24)) << endl;
    cout << (ob.q(8)) << endl;
}

入力

クラスを [0,1,1,0,0,1,0] と [0,5,10,15,20,25,30] で初期化します。
その後、q() メソッドを以下の順に呼び出します:
q(3)
q(12)
q(25)
q(15)
q(24)
q(8)

出力

0
1
1
0
0
1