概要

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

考察

問題は、各利用者が何日来館したかを数え、その日数が \(K\) 以上かどうかを判定することです。制約が \(N, D \leq 100\) と小さいため、素朴なアプローチ（各利用者について毎日来館したか調べる）でも十分高速に動作します。重要なのは、各日の来館者リストを正しく読み取り、各利用者の来館日数を正確にカウントすることです。

アルゴリズム

1. サイズ \(N+1\) の配列 attendance を用意し、各利用者の来館日数を0で初期化します。
2. \(D\) 日分のデータを読み取り、各日について来館者リストを処理します。
3. 各来館者に対して、対応する attendance のインデックスの値を1増やします。
4. すべての日を処理した後、attendance を調べ、値が \(K\) 以上の利用者をリストに追加します。
5. リストが空なら -1 を、そうでなければ昇順（番号順）に出力します。

計算量

• 時間計算量: \(O(D \times M_{\text{max}})\)
  • 各日について最大 \(M_j\) 人の来館者を処理するため。\(M_{\text{max}} \leq N \leq 100\) なので、最大 \(100 \times 100 = 10000\) 回の操作で済みます。
• 空間計算量: \(O(N)\)
  • 利用者の来館日数を記録する配列のサイズが \(N+1\) であるため。

実装のポイント

• 入力の最初の行とそれ以降の行で形式が異なることに注意します。

• \(M_j = 0\) の場合は来館者が0人なので、何も処理しないようにします。

• 利用者番号は1-indexedなので、配列のインデックス1から\(N\)までを使用します。

• 最後に、常連利用者のリストが空かどうかをチェックし、適切に出力します。

  ソースコード

def main():
    import sys
    data = sys.stdin.read().splitlines()
    if not data:
        print(-1)
        return
        
    first_line = data[0].split()
    N = int(first_line[0])
    D = int(first_line[1])
    K = int(first_line[2])
    
    attendance = [0] * (N + 1)
    
    for i in range(1, D + 1):
        parts = data[i].split()
        if not parts:
            continue
            
        M_j = int(parts[0])
        if M_j == 0:
            continue
            
        visitors = list(map(int, parts[1:1 + M_j]))
        for visitor in visitors:
            if 1 <= visitor <= N:
                attendance[visitor] += 1
    
    frequent_visitors = []
    for i in range(1, N + 1):
        if attendance[i] >= K:
            frequent_visitors.append(i)
    
    if frequent_visitors:
        print(" ".join(map(str, frequent_visitors)))
    else:
        print(-1)

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。