集合型を学ぼう！

問題へのリンク

問題概要

$N$ 個の文字列 $S_{1}, S_{2}, \dots, S_{N}$ がこの順に与えられる。

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

制約

$1 \le N \le 10^{15}$
$1 \le |S_{i}| \le 15$

解説

0-indexed で考えます。つまり、文字列を $S_{0}, S_{1}, \dots, S_{N-1}$ とします（出力するときには 1 を足します）。

まずは計算量のことを考えずに解いてみましょう。一番自然な解法は次のように、各 $i = 0, 1, \dots, N-1$ に対して、 $S_{i}$ がそれ以前に登場しているかを判定する方法でしょう。

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 となるはずです。それは、このコードの計算量が $O(N^{2})$ であるためです。なお、計算量について知らない方は、次の記事を読んでみてください。

qiita.com

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

「 $S_{i}$ がすでに登場しているかどうかを判定する」

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

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

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

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

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

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

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

コード

#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);
    }
}

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

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

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

問題概要

制約

解説

コード