AtCoder - Sign Up Requests -

問題リンク

AtCoder Typical90 D

解法

この問題では、ユーザー名の重複を防いで、初めて受理された日を記録するというタスクを効率的に処理します。

1. ユーザ名の管理

ユーザー名がすでに登録されているかどうかを高速に確認するために、set（集合）を使います。setは要素の追加・検索が平均 ( O(1) ) で行えるので、数が多くても高速に処理できます。

2. 処理の流れ

• ユーザー名の一覧を1日ずつ確認し、まだ登録されていないユーザー名なら、その名前をsetに追加し、初めて受理された日（インデックス + 1）を記録します。
• 最終的に、記録された日をリストとして出力します。

実装

def find_accepted_days(N, usernames):
    registered = set()  # 登録済みユーザ名を管理するセット
    accepted_days = []  # 受理された日のリスト

    for i in range(N):
        # もしユーザ名が登録されていなければ、その日を記録する
        if usernames[i] not in registered:
            registered.add(usernames[i])
            accepted_days.append(i + 1)  # 1日目から始まるので i + 1

    return accepted_days

# 入力の読み込み
N = int(input())  # ユーザー数の入力
usernames = [input().strip() for _ in range(N)]  # 各ユーザ名の入力

# 受理された日を取得
result = find_accepted_days(N, usernames)

# 結果の出力
for day in result:
    print(day)

説明

1. registered = set(): すでに登録されたユーザー名を管理するためのsetです。重複を自動的に排除します。
2. accepted_days = []: 受理された日を記録するリストです。
3. if usernames[i] not in registered: 現在のユーザー名がまだ登録されていない場合、その名前をregisteredに追加し、受理された日（i + 1日目）をaccepted_daysに記録します。
4. 結果の出力: 最後に、accepted_daysに記録された日を順番に出力します。

計算量

• 各ユーザ名の登録と検索はsetを使用しているため、平均計算量は ( O(1) ) です。
• 全体の計算量は ( O(N) ) となり、最大 ( N = 100,000 ) に対しても十分高速に処理できます。