概要

\(N\) 人の子供が円形に座り、全員が同時にカードを時計回りに隣へ渡す操作を \(K\) 回行った後、各子供が持つカードの番号を求める問題です。

考察

重要な気づき：カードの移動方向

カードは時計回りに渡されます。つまり、子供 \(i\) が持っていたカードは子供 \(i+1\) に移動します。

これは言い換えると、操作1回ごとに、各カードの位置が時計回りに1つ進むということです。

具体例で確認（\(N = 4\) の場合）

操作回数	子供1	子供2	子供3	子供4
\(K=0\)	1	2	3	4
\(K=1\)	4	1	2	3
\(K=2\)	3	4	1	2

\(K=1\) の後、子供1が持っているのはカード4（＝子供 \(N\) のカード）です。カードが時計回りに1つ進むため、子供 \(i\) の視点から見ると、反時計回りに \(K\) 個前の子供のカードが手元に来ることになります。

数式で表現

\(K\) 回操作後に子供 \(i\) が持つカードの番号は、元々そのカードを持っていた子供の番号です。子供 \(i\) から反時計回りに \(K\) 個前の子供は：

\[\text{カード番号} = ((i - 1 - K) \bmod N) + 1\]

ここで \(i-1\) として \(0\)-indexed に変換し、\(K\) を引いてから \(\bmod N\) を取り、最後に \(+1\) して \(1\)-indexed に戻しています。

素朴なシミュレーションではなぜダメか

\(K\) は最大 \(10^{18}\) と非常に大きいため、1回ずつ操作をシミュレーションすると \(O(NK)\) となり、到底間に合いません。上記の数式を使えば、各子供について \(O(1)\) で直接答えを計算できます。

アルゴリズム

1. \(N\) と \(K\) を入力として受け取る。
2. 各子供 \(i\)（\(1 \leq i \leq N\)）について、\(((i - 1 - K) \bmod N) + 1\) を計算して出力する。

Python の % 演算子は負の数に対しても正の剰余を返すため（例：\((-3) \% 4 = 1\)）、特別な処理は不要です。

計算量

• 時間計算量: \(O(N)\) — 各子供について \(O(1)\) の計算を \(N\) 回行う
• 空間計算量: \(O(1)\) — 追加のデータ構造は不要

実装のポイント

• Python の % 演算子は被除数が負でも非負の結果を返すため、\(i - 1 - K\) が負になっても正しく動作します。例えば \(N=4, K=3, i=1\) のとき \((1 - 1 - 3) \% 4 = (-3) \% 4 = 1\) となり、答えは \(1 + 1 = 2\) です。

• \(K\) が \(10^{18}\) と巨大でも、Python は多倍長整数を標準でサポートしているため、オーバーフローの心配はありません。

• 0-indexed と 1-indexed の変換（\(-1\) してから \(\bmod\) を取り、\(+1\) する）は円環上の問題でよく使うテクニックです。

  ソースコード

N, K = map(int, input().split())
for i in range(1, N + 1):
    print((i - 1 - K) % N + 1)

---

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