概要

円形に並んだ \(N\) 人の子供たちが、持っているカードを隣の人に渡す操作を \(K\) 回繰り返した後の状態を求める問題です。\(K\) が非常に大きいため、愚直なシミュレーションではなく数学的な規則性を見つける必要があります。

考察

1. カードの動きを観察する

例えば \(N=3\) のとき、カードがどのように動くか考えてみましょう。 - 最初：子供 1 はカード 1、子供 2 はカード 2、子供 3 はカード 3 を持っています。 - 1回目：全員が時計回りに渡すので、 - 子供 1 は子供 3 からカード 3 を受け取る - 子供 2 は子供 1 からカード 1 を受け取る - 子供 3 は子供 2 からカード 2 を受け取る - 2回目：さらに時計回りに渡すと、 - 子供 1 は子供 3 からカード 2 を受け取る - 子供 2 は子供 1 からカード 3 を受け取る - 子供 3 は子供 2 からカード 1 を受け取る

このように、操作を 1 回行うごとに、各子供が持っているカードの番号は「反時計回りに 1 つ隣の人が持っていたもの」に変わっていきます。

2. 素朴なアプローチの限界

操作を 1 回行うのに \(O(N)\) の時間がかかります。これを \(K\) 回繰り返すと、全体の計算量は \(O(NK)\) となります。 本問題では \(N \leq 2 \times 10^5\)、\(K \leq 10^{18}\) であるため、\(O(NK)\) では到底制限時間に間に合いません。\(K\) の値に依存しない、あるいは \(K\) が非常に大きくても高速に計算できる方法が必要です。

3. 数式での表現

\(K\) 回の操作後、子供 \(i\) が持っているカードが何番であるかを直接計算します。 カードが時計回りに \(K\) 回移動するということは、子供 \(i\) の位置には、もともと \(K\) 個手前（反時計回り側） にいた子供のカードがやってくることになります。

これを数式（0-indexed、つまり 0 から \(N-1\) 番として計算）で表すと、子供 \(i\) が持っているカードの初期位置は以下のようになります。 $\((i - K) \pmod N\)$

Python などの言語では、負の数に対する剰余演算（%）が数学的な定義通り（結果が \(0\) 以上 \(N-1\) 以下になるよう）に行われるため、この式をそのまま利用できます。

アルゴリズム

1. 1 番目から \(N\) 番目までの各子供 \(i\) について、以下の計算を行います。
2. 計算を簡単にするため、一旦 0-indexed に直します： current_pos = i - 1
3. \(K\) 回操作した後にその位置に来るカードの初期位置を求めます： start_pos = (current_pos - K) % N
4. 1-indexed に戻すために 1 を加算します： card_number = start_pos + 1
5. 全員の計算結果を順に出力します。

計算量

• 時間計算量: \(O(N)\) \(N\) 人の子供それぞれについて定数時間で計算が終わるため、全体の計算量は \(N\) に比例します。\(K\) がどれほど大きくても計算時間は変わりません。
• 空間計算量: \(O(N)\) 結果を保持してまとめて出力する場合、リスト等に \(N\) 要素分を格納するため \(O(N)\) となります。

実装のポイント

• 大きな \(K\) の扱い: \(K\) は最大 \(10^{18}\) と非常に大きいですが、剰余演算を用いることで問題なく扱えます。

• 高速な入出力: \(N\) が最大 \(2 \times 10^5\) と比較的大きいため、Python では sys.stdin.read や sys.stdout.write を使用して入出力を高速化するのが無難です。

• 負の数の剰余: (i - 1 - K) % N の計算において、i - 1 - K が負になることがありますが、Python の % 演算子は期待通り \(0\) 以上 \(N-1\) 以下の値を返してくれます。他の言語（C++ など）では負の結果が返ることがあるため、(i - 1 - K % N + N) % N のように書く必要があります。

  ソースコード

import sys

def solve():
    # 入力を取得
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    k = int(input_data[1])
    
    # K回操作した後の子供 i (1-indexed) が持っているカードは、
    # 最初、子供 (i - 1 - K) % N + 1 が持っていたカードである。
    # 最初の時点では子供 x はカード x を持っているため、
    # 答えは ((i - 1 - K) % N) + 1 となる。
    
    results = []
    for i in range(1, n + 1):
        # 0-indexed で計算し、最後に 1 を足して 1-indexed に戻す
        card_index = (i - 1 - k) % n
        results.append(str(card_index + 1))
    
    # 結果を出力
    sys.stdout.write('\n'.join(results) + '\n')

if __name__ == '__main__':
    solve()

---

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