概要

カードは毎回「全員同時に時計回りへ 1 つずつ」動くので、全体として見るとカードの並びが円環上で回転しているだけです。
したがって、\(K\) 回の操作をそのままシミュレーションする必要はなく、各子供が最終的にどのカードを持つかを式で直接求められます。

考察

まず、操作を 1 回だけ行ったときを考えます。

最初の状態は

• 子供 \(1\) はカード \(1\)
• 子供 \(2\) はカード \(2\)
• \(\cdots\)
• 子供 \(N\) はカード \(N\)

を持っています。

ここで全員が同時に時計回りの隣へ渡すと、

• 子供 \(1\) は子供 \(N\) からカード \(N\) を受け取る
• 子供 \(2\) は子供 \(1\) からカード \(1\) を受け取る
• 子供 \(3\) は子供 \(2\) からカード \(2\) を受け取る
• \(\cdots\)

となります。

つまり、操作 1 回後に子供 \(i\) が持つのは、もともと子供 \(i-1\) が持っていたカードです
（ただし \(i=1\) のときは \(i-1=0\) ではなく子供 \(N\) を意味します）。

例えば \(N=5\) のとき：

• 初期状態: \([1,2,3,4,5]\)
• 1 回後: \([5,1,2,3,4]\)
• 2 回後: \([4,5,1,2,3]\)

となり、毎回「配列が右に 1 つ回転」しているように見えます。

重要な気づき

\(K\) 回後、子供 \(i\) が持つカードは

• 1 回ごとに 1 つ前の子供のカードになる
• それを \(K\) 回繰り返す

ので、子供 \(i\) はもともと子供 \(i-K\) が持っていたカードを持つことになります。
円形なので、添字は \(N\) で割った余りで考えればよいです。

1-indexed で書くと、答えは

\[ ((i-K-1) \bmod N) + 1 \]

です。

素朴な方法がダメな理由

毎回カードの移動をそのままシミュレーションすると、1 回の操作に \(O(N)\)、これを \(K\) 回行うので \(O(NK)\) かかります。

しかし制約では

• \(N \le 2 \times 10^5\)
• \(K \le 10^{18}\)

なので、\(K\) 回のシミュレーションは到底間に合いません。

どう解決するか

円形に \(N\) 回回すと元の状態に戻るので、実質的には

\[ K \bmod N \]

回だけ考えれば十分です。

そのうえで、各子供 \(i\) に対して式

\[ ((i-K-1) \bmod N) + 1 \]

を使って直接答えを出せば、全体を \(O(N)\) で求められます。

アルゴリズム

1. \(K\) を \(K \bmod N\) に置き換える
2. 各子供 \(i=1,2,\dots,N\) について、持っているカード番号を $\( ((i-K-1) \bmod N) + 1 \)$ で計算する
3. 順に出力する

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 円形なので、\(N\) 回操作すると元に戻ります。そのため最初に K %= N としてよいです。

• 1-indexed の番号をそのまま扱うと式が少しずれるので、

  
  (i - K - 1) % N + 1
  

  の形にするときれいに書けます。

• Python の % は負の数でも非負の余りを返すので、i-K-1 が負になっても正しく処理できます。

  ソースコード

import sys

def main():
    N, K = map(int, sys.stdin.readline().split())
    K %= N
    ans = [str((i - K - 1) % N + 1) for i in range(1, N + 1)]
    sys.stdout.write("\n".join(ans))

if __name__ == "__main__":
    main()

---

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