概要

整理番号が \(K\) の倍数（\(K, 2K, 3K, \ldots\)）の来場者だけを選び、その人たちのくじ引き券番号 \(A_i\) を順番に出力する問題です。

考察

重要な点は、「景品を渡す対象」は 整理番号（= 何番目に引いたか） で決まることです。つまり、条件を満たすのは \(i\) が \(K\) の倍数である人で、出力すべき値はその人の券番号 \(A_i\) です。

例えば \(N=8, K=3\) のとき、対象の整理番号は \(3,6\) なので、出力は \(A_3, A_6\) になります。

素朴に全員 \(i=1\) から \(N\) まで見て「\(i\) が \(K\) の倍数か？」を判定する方法でも \(O(N)\) で間に合います。しかし、より直接的に「\(K\) の倍数だけを列挙」すれば、無駄な判定をせずに済み、実装も明快になります（\(K, 2K, 3K, \ldots\) と進める）。

また、\(N\) が最大 \(2\times 10^5\) なので、入力は sys.stdin.buffer.read() でまとめて読むと高速で安全です。

アルゴリズム

1. 入力で \(N, K\) と配列 \(A\) を受け取る。
2. 整理番号 \(i\) を \(i=K, 2K, 3K, \ldots\) と \(N\) 以下まで増やしながら走査する。
3. 各 \(i\) について、対応する券番号は \(A_i\) だが、Python のリストは 0-indexed なので A[i-1] を取り出す。
4. 取り出した値を順番に並べ、スペース区切りで出力する。
5. 該当者がいない場合（理論上は \(K \le N\) なので必ず1人以上いるが）、空配列なら空文字を出力しても問題ない。

計算量

• 時間計算量: \(O(\lfloor N/K \rfloor)\)（\(K\) の倍数の人数分だけ処理する）
• 空間計算量: \(O(\lfloor N/K \rfloor)\)（出力用に結果を保持する。入力配列 \(A\) は別途 \(O(N)\)）

実装のポイント

• 整理番号は 1-indexed、配列は 0-indexedなので A[i-1] に注意する。

• range(K, N+1, K) を使うと、\(K\) の倍数だけを自然に列挙できる。

• 出力は join を使ってまとめて出すと高速（1つずつ print するより安定）。

  ソースコード

import sys

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

    res = [str(A[i-1]) for i in range(K, N + 1, K)]
    sys.stdout.write(" ".join(res))

if __name__ == "__main__":
    main()

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