概要

各利用者が「\(D\) 日のうち何日来館したか」を数え、来館日数が \(K\) 日以上の利用者番号を昇順に出力する問題です。

考察

重要なのは「来館回数」ではなく「来館した日数（＝その日の記録に含まれているか）」を数えることです。
ただし本問題では「同じ日に同じ利用者が複数回記録されない」と保証されているため、各日のリストに現れた利用者を 1 回ずつ数え上げれば、そのまま“来館した日数”になります。

素朴に「各利用者 \(i\) について、全日程を見てその日に来ているかを探す（例えば線形探索）」のように書くと、実装が回りくどくなりがちです（入力のリストを何度も探すことになる）。
そこで、入力を読んだ順に「登場した利用者のカウントを 1 増やす」だけにすると、シンプルかつ確実に解けます。

例： - \(D=3, K=2\) - 1日目: {1,3} - 2日目: {2,3} - 3日目: {3} → 利用者3は3日来館、利用者1は1日、利用者2は1日
→ \(K=2\) 以上は「3」だけ

アルゴリズム

1. 長さ \(N\) の配列 cnt を用意し、cnt[i] を「利用者 \(i\) が来館した日数」とする（初期値 0）。
2. 各日について入力を読み、来館者番号 \(s\) が現れるたびに cnt[s] += 1 とする。
   • 同じ日に同じ番号が重複しないため、これで「日数」を正しく数えられる。
3. \(1 \le i \le N\) のうち cnt[i] >= K を満たすものを昇順に列挙して出力する。
4. 条件を満たす利用者がいなければ -1 を出力する。

計算量

• 時間計算量: \(O\!\left(\sum_{j=1}^{D} M_j + N\right)\)
  （入力に登場する人数の総和だけ加算し、最後に \(N\) 人をチェック）
• 空間計算量: \(O(N)\)
  （カウント配列 cnt のみ）

実装のポイント

• M_j = 0 の日があり得るので、「人数 \(M\) を読んだら、次に \(M\) 個だけ番号を読む」を徹底すると安全です。

• 出力は昇順指定ですが、i=1..N の順に条件判定すれば自然に昇順になります。

• 条件を満たす人が 0 人のときだけ -1 を出力する分岐を忘れないようにします。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    idx = 0
    N = data[idx]; D = data[idx+1]; K = data[idx+2]
    idx += 3

    cnt = [0] * (N + 1)
    for _ in range(D):
        M = data[idx]
        idx += 1
        for _ in range(M):
            s = data[idx]
            idx += 1
            cnt[s] += 1

    ans = [str(i) for i in range(1, N + 1) if cnt[i] >= K]
    if ans:
        print(" ".join(ans))
    else:
        print("-1")

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。