概要

\(N\) 人の来場者が順番に整理番号 \(1, 2, \dots, N\) を受け取ります。整理番号が \(K\) の倍数（\(K, 2K, 3K, \dots\)）である来場者が持つ「くじ引き券の番号」を、順番に出力する問題です。

考察

この問題で重要なのは、「どの位置にあるデータを出力すべきか」を正確に把握することです。

整理番号 \(i\) 番目の人のくじ引き券の番号は \(A_i\) です。景品をもらえるのは整理番号が \(K\) の倍数の人なので、出力すべき番号は以下の通りになります： - 1人目：\(A_K\) - 2人目：\(A_{2K}\) - 3人目：\(A_{3K}\) - …

例えば、\(N=6, K=2\) で、くじ引き券の番号が \([10, 20, 30, 40, 50, 60]\) の場合、整理番号が \(2\) の倍数（\(2, 4, 6\)）である人の番号、つまり \(A_2=20, A_4=40, A_6=60\) を出力します。

\(N\) が最大 \(2 \times 10^5\) と大きいため、すべての来場者を 1 人ずつ確認して「整理番号が \(K\) で割り切れるか？」を判定しても十分間に合いますが、より効率的には \(K\) 番目ごとにジャンプして値を取得するのが理想的です。

アルゴリズム

1. 入力から \(N, K\) および \(A_1, \dots, A_N\) を取得します。
2. 配列（リスト）の中から、インデックスが \(K\) の倍数に対応する要素を順番に取り出します。
   • プログラミング言語の多くは 0 始まりのインデックスを使用するため、整理番号 \(K\) はインデックス \(K-1\) に対応することに注意してください。
3. 取り出した番号をスペース区切りで出力します。

Python の場合、リストのスライス機能 list[start:end:step] を使うことで、特定の刻み幅（ステップ）で要素を非常に高速かつ簡潔に抽出できます。

計算量

• 時間計算量: \(O(N)\)
  • 全データの読み込みに \(O(N)\)、景品対象者の抽出と出力に \(O(N/K)\) かかります。全体として \(O(N)\) となります。
• 空間計算量: \(O(N)\)
  • 入力された \(N\) 個の要素を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: \(N\) が大きいため、Python では sys.stdin.read().split() を使って一括で入力を取得すると実行時間を短縮できます。

• スライスの活用: data[k+1 :: k] のように書くことで、「整理番号 \(K\) に対応する位置から最後まで、\(K\) 個飛ばしで取得する」という処理が 1 行で記述できます。

  • 今回のコードでは data[0] が \(N\)、data[1] が \(K\)、data[2] が \(A_1\) となっているため、最初の対象 \(A_K\) は data[2 + (K-1)] つまり data[K+1] に位置しています。

• アンパック出力: print(*ans) とすることで、リストの中身をスペース区切りで展開して出力できます。

  ソースコード

import sys

def main():
    # 標準入力からすべてのデータを読み込み、空白文字（スペース、改行など）で分割してリストにします。
    # N（来場者数）と K（景品の倍数）が20万程度と大きいため、一括読み込みが効率的です。
    data = sys.stdin.read().split()
    
    # 入力が空の場合や不足している場合の例外処理
    if len(data) < 2:
        return
    
    # K はリストの2番目の要素（インデックス 1）です。
    k = int(data[1])
    
    # くじ引き券の番号 A_1, A_2, ..., A_N は data[2] 以降に格納されています。
    # 整理番号が K の倍数である来場者は、K番目、2K番目、3K番目... の来場者です。
    # これらは A_K, A_2K, A_3K, ... のチケット番号を持っています。
    # リスト data におけるそれぞれのインデックスは以下の通りです：
    # A_1  -> インデックス 2
    # A_2  -> インデックス 3
    # ...
    # A_K  -> インデックス 2 + (K - 1) = K + 1
    # A_2K -> インデックス 2 + (2K - 1) = 2K + 1
    # したがって、インデックス K + 1 から K 刻みでスライスすることで、
    # 景品をもらえる来場者のチケット番号を順番に抽出できます。
    ans = data[k + 1 :: k]
    
    # 結果が存在する場合、スペース区切りで1行に出力します。
    # Pythonの * 演算子（アンパック）を使うことで、リストの要素をスペース区切りで出力できます。
    if ans:
        print(*(ans))

if __name__ == '__main__':
    main()

この解説は gemini-3-flash-preview によって生成されました。