解法

主要なプログラミング言語の多くにおいては、文字列の辞書順による比較は標準ライブラリに含まれる関数や言語機能として提供されています。それらを用いて簡潔に実装することができます。例えば C++ では、 std::string 変数同士の < による比較は辞書順比較です。

各ユーザーのレートの総和 \(T\) は、 for 文などによるループで求めることができます。それから \(T \bmod N\) を計算することで、勝者の番号を求めることができます。

さらに、各ユーザーにどの番号が割り当てられているかを求める必要があります。これは、各ユーザーの名前を辞書順に並び替えることで求められます。多くの言語にはソートを行う関数があるので、それを用いると簡潔です。例えば C++ では以下のように実装することができます。

#include <bits/stdc++.h>

using namespace std;

int main() {
    // 入力
    int n;
    cin >> n;
    vector<string> s(n);
    vector<int> c(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i] >> c[i];
    }

    // 文字列の辞書順ソート
    sort(s.begin(), s.end());

    // 勝者の番号を求める
    int sum_rating = 0;
    for (const int e : c) {
        sum_rating += e;
    }
    const int winner = sum_rating % n;

    // 出力
    cout << s[winner] << endl;
}

文字列をソートする計算量について

\(\displaystyle M = \sum_{i=1}^{N} |S_i| \) とおきます。

マージソートを用いれば、計算量は \(O(M \log N)\) です。これは \(2\) つの文字列 \(a, b\) の辞書順比較は計算量 \(O(\min(|a|, |b|))\) でできることによります。

C++ の std::stable_sort は、仕様上は保証されませんがほぼ確実にマージソートで実装されています。これを用いることができます。

GCC libstdc++ の std::sort は文字列比較でも高速に動くことが多いです。実装されているアルゴリズムが実際に最悪ケースでも \(O(M \log N)\) であるかどうかはわからない 、というのがコミュニティの共通認識だと思います。少なくとも \(\displaystyle O((\max_{1 \leq i \leq N} |S_i|) N \log N)\) ではあるので、この問題では十分高速です。

\(O(M)\) で解くこともできます。SA-IS を使う方法などがあります。