C++でリーダーボードクラスを設計する方法

ここでは、ゲームなどで使われるリーダーボード（順位表）を管理する Leaderboard クラスを C++ で設計します。このクラスには、次の3つの操作が必要です。

• addScore(playerId, score) — 指定したプレイヤーのスコアに score を加算してリーダーボードを更新します。該当する ID のプレイヤーがまだ存在しない場合は、そのスコアで新規登録します。
• top(K) — 現在の上位 K 人のプレイヤーのスコア合計を返します。
• reset(playerId) — 指定した ID のプレイヤーのスコアを 0 にリセットします。この関数が呼ばれる時点で、そのプレイヤーはすでにリーダーボードに登録されていることが保証されています。

初期状態では、リーダーボードは空である必要があります。

動作例

以下のような一連の操作を考えてみましょう。

Leaderboard leaderboard = new Leaderboard();
leaderboard.addScore(1,73); // [[1,73]]
leaderboard.addScore(2,56); // [[1,73],[2,56]]
leaderboard.addScore(3,39); // [[1,73],[2,56],[3,39]]
leaderboard.addScore(4,51); // [[1,73],[2,56],[3,39],[4,51]]
leaderboard.addScore(5,4);  // [[1,73],[2,56],[3,39],[4,51],[5,4]]
leaderboard.top(1);   // 73 を返す
leaderboard.reset(1); // [[2,56],[3,39],[4,51],[5,4]]
leaderboard.reset(2); // [[3,39],[4,51],[5,4]]
leaderboard.addScore(2,51); // [[2,51],[3,39],[4,51],[5,4]]
leaderboard.top(3);   // 141 (= 51 + 51 + 39) を返す

解法のアプローチ

この問題は「遅延削除（Lazy Deletion）」というテクニックを使うと効率的に解けます。古いスコアのエントリを都度削除せずに残しておき、取り出す際に現在のスコアと一致するかどうかで有効か無効かを判定する方法です。

手順

• (スコア, プレイヤーID) のペアを格納する優先度付きキュー pq と、キー・値とも int 型のマップ m を定義します。コンストラクタではマップをクリアし、キューに要素が残っていればすべて取り除きます。
• addScore() メソッド：
  • playerId がマップに存在する場合は、m[playerId] を score 分だけ加算します。
  • 存在しない場合は、m[playerId] = score として新規登録します。
  • 最後に、ペア (m[playerId], playerId) を pq に挿入します。
• top() メソッド：
  • ペアを一時保存するベクトル temp を用意し、sum を 0 で初期化します。
  • k が 0 になるまで以下を繰り返します。
    • pq の先頭要素を curr として取り出し、pq から削除します。
    • m[curr.second] == curr.first（＝最新のスコアと一致する＝有効なエントリ）の場合のみ、k を 1 減らし、sum に curr.first を加算し、curr を temp に退避します。
  • 処理後、temp の全要素を pq に戻します。
• reset() 関数：m[playerId] = 0 とするだけです。古いエントリは pq に残りますが、次回 top() 実行時にスコア不一致のため自動的にスキップされます。

C++での実装例

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Leaderboard {
public:
    priority_queue< pair<int,int> > pq;
    map< int, int > m;
    Leaderboard() {
        m.clear();
        while(!pq.empty()) pq.pop();
    }
    void addScore(int playerId, int score) {
        if(m.find(playerId) != m.end()){
            m[playerId] += score;
        }
        else m[playerId] = score;
        pq.push({m[playerId], playerId});
    }
    int top(int k) {
        vector< pair<int,int> > temp;
        int sum = 0;
        while(k){
            pair<int,int> curr = pq.top();
            pq.pop();
            if(m[curr.second] == curr.first){
                k--;
                sum += curr.first;
                temp.push_back(curr);
            }
        }
        for(int i = 0; i < temp.size(); i++) pq.push(temp[i]);
        return sum;
    }
    void reset(int playerId) {
        m[playerId] = 0;
    }
};
main(){
    Leaderboard ob;
    ob.addScore(1,73);
    ob.addScore(2,56);
    ob.addScore(3,39);
    ob.addScore(4,51);
    ob.addScore(5,4);
    cout << ob.top(1) << endl;
    ob.reset(1);
    ob.reset(2);
    ob.addScore(2,51);
    cout << ob.top(2) << endl;
}

入力

リーダーボードを初期化し、main() 関数内で各メソッドを呼び出して結果を確認します。

出力

73
102

まとめ

この実装では、addScore() は O(log n)、top(K) は O(n log n)、reset() は O(log n) の計算量で動作します。遅延削除により、リセットやスコア更新のたびにキュー全体を再構築する必要がないため、シンプルかつ実用的なリーダーボード設計となっています。