けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 251 C - Poem Online Judge (4Q, 灰色, 300 点)

意外と整理するのが大変だと思う。map を使って整理しようとするのも自然だが、もうちょっと簡単に解くことを考えよう。

問題概要

文字列を投稿すると得点が与えられるコンテストに、 N 個の文字列  S_{1}, S_{2}, \dots, S_{N} がこの順に投稿され、それぞれ  T_{1}, T_{2}, \dots, T_{N} 点が与えられた。

各文字列は、過去に同じ文字列が投稿されていないとき、オリジナルであるという。オリジナルな投稿文字列のうち、最多得点を獲得したものが何番目に投稿されたものであるかを答えよ(タイがある場合はそのうちの最も早いもの)。

制約

  •  1 \le N \le 10^{5}

考えたこと

最初は、map を使って、各文字列のオリジナルの得点と、オリジナルの投稿順を整理することを考えた。それでも解けるが、もっと簡単に解ける。

単純に次のように考えればよい。


 T_{i} が最大となる  i(タイがあればそのうちの最小値)を求めよ。

ただし、 S_{i} がオリジナルではないような  i は除く。


 S_{i} がオリジナルではないような  i は除くためには、set<string> 型が使える。全体の計算量は  O(N \log N) となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, T;
    string S;
    cin >> N;
    int max_score = 0, res;
    set<string> already;
    for (int i = 0; i < N; i++) {
        cin >> S >> T;
        if (already.count(S)) continue;
        already.insert(S);

        if (max_score < T) {
            max_score = T;
            res = i;
        }
    }
    cout << res+1 << endl;
}