概要

\(D\) 日間の来館記録から、\(K\) 日以上来館した利用者（常連利用者）を特定し、その利用者番号を昇順に出力する問題。

考察

この問題では、各利用者が何日来館したかを正確にカウントする必要があります。素朴な方法として、毎回来館者リストを見て、各利用者の登場回数を数えることも考えられますが、それだと効率的ではありません。

重要な観察は、「各利用者の来館日数」だけが必要であり、来館した具体的な日は不要だということです。そのため、各日ごとに来館者を読み込みながら、利用者ごとに来館日数をカウントしていけば良いです。

ただし、同じ日に同じ人が複数回記録されることはないという制約がありますが、念のため入力時に set を使って重複を除外しておくと安全です（実際には不要ですが、バグ防止のため推奨）。

最後に、来館日数が \(K\) 日以上の利用者を番号順に抽出して出力すれば完了です。もし該当者がいなければ -1 を出力します。

アルゴリズム

1. 各利用者の来館日数を記録するための配列 visit_count を用意する（サイズは \(N+1\) にしてインデックスを1からNに対応させる）。
2. 各日ごとに来館者を読み込み、各来館者の visit_count をインクリメントする。
3. 全日程を処理した後、visit_count が \(K\) 以上の利用者を番号順にリストアップする。
4. リストが空なら -1、そうでなければ昇順にスペース区切りで出力する。

計算量

• 時間計算量: \(O(D \cdot M_{\text{avg}} + N)\)
  （\(M_{\text{avg}}\) は1日あたりの平均来館者数）
• 空間計算量: \(O(N + M_{\text{max}})\)
  （来館者リストの一時保持分とカウンタ配列）

実装のポイント

• 利用者番号は1-indexedなので、配列のサイズは \(N+1\) にする。

• 各日ごとの入力を処理する際に、M_j = 0 の場合にアクセスエラーにならないように注意する。

• 念のため、入力の来館者リストを set() で重複を除外してからカウントすることで堅牢性を高める。

  ソースコード

# 入力読み込み
N, D, K = map(int, input().split())

# 各利用者の来館日数をカウントする配列
visit_count = [0] * (N + 1)  # 利用者番号1〜Nに対応させるためN+1

# 各日ごとの来館記録を処理
for _ in range(D):
    line = list(map(int, input().split()))
    M = line[0]
    if M > 0:
        visitors = line[1:]
        # 同じ日に同じ利用者が複数回記録されることはないとされているが、
        # 一応setで重複を除外してからカウント
        unique_visitors = set(visitors)
        for user in unique_visitors:
            visit_count[user] += 1

# 常連利用者を判定（来館日数がK日以上）
regular_users = []
for user_id in range(1, N + 1):
    if visit_count[user_id] >= K:
        regular_users.append(user_id)

# 結果出力
if regular_users:
    print(' '.join(map(str, regular_users)))
else:
    print(-1)

この解説は qwen3-coder-480b によって生成されました。