概要

整理番号が \(K\) の倍数である来場者を順番に見つけ、その来場者のくじ引き券の番号を出力する問題です。

考察

この問題で重要なポイントは以下の通りです：

1. 整理番号と配列のインデックスの関係: \(i\) 番目に福引を引いた来場者の整理番号は \(i\) です。配列 \(A\) は0-indexedなので、整理番号 \(i\) の来場者のくじ引き券番号は \(A[i-1]\) に格納されています。

2. 景品をもらえる条件: 整理番号が \(K\) の倍数、つまり \(K, 2K, 3K, \ldots\) 番目に福引を引いた人が景品をもらえます。

3. 出力の順番: 景品を渡す順番、すなわち整理番号が小さい順（\(K, 2K, 3K, \ldots\)）に出力する必要があります。

具体例で確認しましょう： - \(N = 5, K = 2\) で \(A = [10, 20, 30, 40, 50]\) の場合 - 整理番号1 → くじ引き券番号10 - 整理番号2 → くじ引き券番号20 ← \(K\) の倍数なので景品あり - 整理番号3 → くじ引き券番号30 - 整理番号4 → くじ引き券番号40 ← \(K\) の倍数なので景品あり - 整理番号5 → くじ引き券番号50 - 出力: 20 40

この問題は単純に \(K\) の倍数となる整理番号を順番に処理すればよいので、素朴なアプローチで十分高速に解けます。

アルゴリズム

1. 整理番号 \(i\) を \(1\) から \(N\) まで順に見ていく
2. \(i\) が \(K\) の倍数かどうかを判定（\(i \mod K = 0\) かどうか）
3. \(K\) の倍数であれば、対応するくじ引き券番号 \(A[i-1]\) を結果リストに追加
4. 最後に結果リストをスペース区切りで出力（空の場合は何も出力しない）

別解: \(K\) の倍数を直接列挙する方法もあります。

for i in range(K, N + 1, K):
    result.append(A[i - 1])

この方法では、\(K, 2K, 3K, \ldots\) と \(K\) ずつ増やしながらループするので、判定処理が不要になります。

計算量

• 時間計算量: \(O(N)\)
  • \(1\) から \(N\) までループして各整理番号を確認するため
  • 別解の場合は \(O(N/K)\) となりますが、最悪ケース（\(K=1\)）では \(O(N)\) です
• 空間計算量: \(O(N/K)\)
  • 結果を格納するリストのサイズ（最大で \(\lfloor N/K \rfloor\) 個の要素）

実装のポイント

• インデックスのずれに注意: 整理番号は \(1\) から始まりますが、Pythonの配列は \(0\) から始まるため、整理番号 \(i\) に対応するくじ引き券番号は A[i-1] です。

• 空の場合の出力: 問題文では「景品を渡す来場者が1人もいない場合は、何も出力しない」とあるため、if result: で空でないことを確認してから出力しています。

• print(*result): リストの要素をスペース区切りで出力する便利な書き方です。

  ソースコード

N, K = map(int, input().split())
A = list(map(int, input().split()))

result = []
for i in range(1, N + 1):
    if i % K == 0:
        result.append(A[i - 1])

if result:
    print(*result)

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