概要

\(D\) 日間の来館記録から、各利用者の来館日数を数え上げ、\(K\) 日以上来館した「常連利用者」を昇順に出力する問題です。

考察

この問題で求められていることを整理すると、以下のステップになります：

1. 各利用者（\(1\) から \(N\)）について、\(D\) 日間で何日来館したかをカウントする
2. カウントが \(K\) 以上の利用者を昇順に出力する

例えば、\(N=5, D=3, K=2\) で以下の来館記録があったとします：

• 1日目: 利用者 1, 3, 5
• 2日目: 利用者 2, 3, 4
• 3日目: 利用者 3, 5

このとき、各利用者の来館日数は：

\(K=2\) 以上来館した利用者は 3 と 5 なので、3 5 と出力します。

この問題は制約が \(N \leq 100\), \(D \leq 100\) と小さいため、素朴に全利用者の出現回数をカウントするだけで十分間に合います。特別なアルゴリズムは不要で、TLE の心配はありません。

アルゴリズム

1. カウント配列を用意する: サイズ \(N+1\) の配列 count を \(0\) で初期化する（インデックス \(1\) から \(N\) を使うため）。
2. 来館記録を読み込みカウントする: \(D\) 日分の記録を1日ずつ読み込み、各日に記録されている利用者番号に対応する count の値を \(1\) 増やす。
3. 常連利用者を抽出する: 利用者番号 \(1\) から \(N\) まで順に調べ、\(count[i] \geq K\) である利用者 \(i\) をリストに追加する（昇順に調べるので自然に昇順になる）。
4. 出力する: リストが空でなければスペース区切りで出力し、空なら -1 を出力する。

計算量

• 時間計算量: \(O(D \times N + N)\)
  • 各日の来館者数の合計は最大 \(D \times N\) であり、全記録を読み込んでカウントするのに \(O(D \times N)\)。最後に \(N\) 人分のカウントを確認するのに \(O(N)\)。
• 空間計算量: \(O(N)\)
  • カウント配列のサイズが \(O(N)\)。

実装のポイント

• 入力の読み込み方: 各日の記録は「最初の数 \(M_j\) が来館者数、続く \(M_j\) 個が利用者番号」という形式です。1行をまとめてリストとして読み込み、先頭要素を \(M_j\)、残りを利用者番号として処理すると簡潔に書けます。

• \(M_j = 0\) の場合: その日の来館者が \(0\) 人のとき、行には 0 のみが与えられます。ループ for i in range(1, M+1) で \(M=0\) なら自然にスキップされるため、特別な処理は不要です。

• インデックスのずれに注意: 利用者番号は \(1\) から始まるため、カウント配列をサイズ \(N+1\) で用意し、インデックス \(0\) は使わないようにすると分かりやすくなります。

  ソースコード

N, D, K = map(int, input().split())
count = [0] * (N + 1)
for _ in range(D):
    line = list(map(int, input().split()))
    M = line[0]
    for i in range(1, M + 1):
        count[line[i]] += 1
result = [i for i in range(1, N + 1) if count[i] >= K]
if result:
    print(*result)
else:
    print(-1)

この解説は claude4.6opus-thinking によって生成されました。