競プロ典型 90 問 027 - Sign Up Requests（5Q, ★2）

集合型を学ぼう！

• 問題へのリンク

問題概要

個の文字列 がこの順に与えられる。

初出の文字列に対して、その添字を出力せよ。

制約

• 
• 

解説

0-indexed で考えます。つまり、文字列を とします（出力するときには 1 を足します）。

まずは計算量のことを考えずに解いてみましょう。一番自然な解法は次のように、各 に対して、 がそれ以前に登場しているかを判定する方法でしょう。

for (int i = 0; i < N; i++) {
    bool already = false;
    for (int j = 0; j < i; j++) {
        if (S[j] == S[i]) already = true;
    }

    if (!already) {
        // 初出だったら index を出力する
        cout << i+1 << endl;
    }
}

このコードでサンプルは通ります。しかし、提出すると TLE となるはずです。それは、このコードの計算量が であるためです。なお、計算量について知らない方は、次の記事を読んでみてください。

qiita.com

それでは、このコードを高速化しましょう。高速化できる余地があるとしたら、

「 がすでに登場しているかどうかを判定する」

という部分ではないでしょうか。ここで、集合型の登場です。C++ の set 型は次のクエリをこなせるデータ構造です（変数名を se とします）。

クエリ	詳細	書き方	計算量
挿入	要素 をデータ構造に挿入する（すでにあれば何もしない）	se.insert(v)
削除	要素 をデータ構造から削除する（すでになければ何もしない）	se.erase(v)
検索	要素 がデータ構造に含まれるかどうかを判定する	if (se.count(v))

なお、ここでの計算量は、データ構造のサイズを とした場合のものです。

このデータ構造のすごいところは、データ構造内に要素 が含まれるかどうかを の計算量で判定できることです。この set 型を用いて、上記のコードは次のように書き直せます。

for (int i = 0; i < N; i++) {
    if (!se.count(S[i])) {
        // 初出だったら index を出力する
        cout << i+1 << endl;
    }

    // S[i] をデータ構造に挿入する
    se.insert(S[i]);
}

挿入や検索に要する計算量は ですので、上記の解法全体の計算量は となります。これであれば、十分間に合います。

コード

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

int main() {
    int N;
    string S;
    set<string> se;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> S;

        if (!se.count(S)) {
            // 初出だったら index を出力する
            cout << i+1 << endl;
        } 
        se.insert(S);
    }
}