問題
$N$ 人が円形に並び $1,\dots,N$ の番号がついている。番号 $1$ から数え始めて $K$ 人目を取り除く。取り除かれた人の次から再び数え始めて $K$ 人目を取り除く——1 人だけ残るまで繰り返す。最後に残る人の番号を求めよ。$T$ 件のクエリに答える。
入力形式
T
N_1 K_1
...
N_T K_T制約
| 変数 | 範囲 | 補足 |
|---|---|---|
| $T$ | $1\le T\le10^5$ | |
| $N_i$ | $1\le N_i\le10^7$ | |
| $K_i$ | $1\le K_i\le10^9$ | |
| クエリの型 | $\sum N_i\le10^7$ か、$K_i\le100$ | どちらかの高速解が使える |
入出力例
入力例1
3
7 3
41 3
100 2出力例1
4
31
73$N=7,K=3$: 取り除かれる順は $3,6,2,7,5,1$ で最後に $4$ が残る。
概念図：$N=7,K=3$ の除去順（実測）
ヒント（段階的開示）
ヒント1（方向性）
list.pop(idx) で実際に消していくシミュレーションは $O(N^2)$（pop が $O(N)$）で $N=10^7$ では不可能。「$N$ 人のときの答え」と「$N-1$ 人のときの答え」の関係を考える。最初の 1 人が消えた瞬間、残りは「消えた人の次を先頭にした $N-1$ 人の問題」になっている。
ヒント2（アプローチ）
0-indexed で $J(n,k)$ を生存者の位置とすると、最初に $(k-1)\bmod n$ が消え、その次が新しい 0 番になるので $J(1)=0,\ J(n)=(J(n-1)+k)\bmod n$。これは $O(N)$。$K$ が小さいときは「1 周で $\lfloor n/k\rfloor$ 人がまとめて消える」ことを使い $n\to n-\lfloor n/k\rfloor$ と一気に減らす $O(K\log N)$ の飛ばし漸化式がある。
ヒント3（誘導）
def josephus_on(n, k): # O(N)
r = 0
for i in range(2, n + 1):
r = (r + k) % i
return r
def josephus_klogn(n, k): # O(K log N)
if n == 1: return 0
if k == 1: return n - 1
if k > n: return (josephus_klogn(n - 1, k) + k) % n
cnt = n // k
res = josephus_klogn(n - cnt, k)
res -= n % k
if res < 0: res += n
else: res += res // (k - 1)
return res模範解答 (Python)
import sys
sys.setrecursionlimit(1 << 20)
def josephus_on(n: int, k: int) -> int:
"""0-indexed の生存者位置。J(n)=(J(n-1)+k) mod n を n=2..N で回す O(N)"""
r = 0
for i in range(2, n + 1):
r = (r + k) % i
return r
def josephus_klogn(n: int, k: int) -> int:
"""0-indexed。1周ぶん (n//k 人) をまとめて消す O(K log N)。k が小さいときに有効"""
if n == 1:
return 0
if k == 1:
return n - 1
if k > n:
return (josephus_klogn(n - 1, k) + k) % n
cnt = n // k # この周で消える人数
res = josephus_klogn(n - cnt, k) # 残り n-cnt 人での答え
res -= n % k # 周の終わりに数え残した n%k 人ぶん座標をずらす
if res < 0:
res += n # 周の末尾側（まだ消えていない n%k 人の区間）に戻る
else:
res += res // (k - 1) # 消えた人のぶん (k-1 人ごとに 1 人) だけ座標が伸びる
return res
def solve(n: int, k: int) -> int:
# k が小さければ飛ばし漸化式、そうでなければ O(N) ループ（分岐の根拠は Step 3 の実測）
if k <= 100:
return josephus_klogn(n, k) + 1
return josephus_on(n, k) + 1
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
for i in range(t):
n = int(data[1 + 2 * i]); k = int(data[2 + 2 * i])
out.append(solve(n, k))
print("\n".join(map(str, out)))
main()Step-by-Step 解説
1漸化式の意味
$n$ 人の円で最初に消えるのは 0-indexed で $(k-1)\bmod n$。その次を新しい 0 番として振り直すと $n-1$ 人の問題。$J(n-1)$ を元の番号に戻すには振り直しで引いた $k$ を足して $\bmod n$。「部分問題の答えを座標変換で戻す」が骨格で、$O(K\log N)$ 版はこれを「1 周まとめて」に拡張しただけ。
$n$ 人の円で最初に消えるのは 0-indexed で $(k-1)\bmod n$。その次を新しい 0 番として振り直すと $n-1$ 人の問題。$J(n-1)$ を元の番号に戻すには振り直しで引いた $k$ を足して $\bmod n$。「部分問題の答えを座標変換で戻す」が骨格で、$O(K\log N)$ 版はこれを「1 周まとめて」に拡張しただけ。
2実測（本ページ作成時に Python で実行）
$1\le N,K\le60$ の乱択 3000 ケースで 3 者完全一致（不一致 0 件）。
| 入力 | シミュレーション | $O(N)$ | $O(K\log N)$ |
|---|---|---|---|
| $N=7,K=3$ | 除去順（0-idx）[2,5,1,6,4,0,3] → 生存 3（1-idx 4） | 3 | 3 |
| $N=41,K=3$ | — | 30（1-idx 31・伝承値と一致） | 30 |
| $N=100,K=2$ | — | 72（1-idx 73） | 閉形式 $2(n-2^{\lfloor\log_2n\rfloor})=72$ と一致 |
3分岐根拠（実測）
$K=3$ では 4 万倍差。ただし $O(K\log N)$ 版は k > n 分岐で 1 人ずつしか減らせず、$K\ge N$ では $O(N)$ 再帰（スタック $N$ 段）に退化する。閾値 100 は「$K\log N\approx2400$ 回の再帰で済む」という導出値で、最適点を測ったわけではない。
| $N=10^7,K=3$ | 所要時間 | 補足 |
|---|---|---|
| $O(N)$ ループ | 0.403 s | 単純ループ $10^7$ 回 |
| $O(K\log N)$ 再帰 | 0.00001 s | 再帰深さ 41（実測） |
4$K=2$ の閉形式
$J(n)=2(n-2^{\lfloor\log_2n\rfloor})$（Concrete Mathematics 1.3 節）。2 進表記の最上位ビットを末尾に回す操作に等しい。$n=1,2,5,8,16,100$ で $O(N)$ 版と一致を実測。
$J(n)=2(n-2^{\lfloor\log_2n\rfloor})$（Concrete Mathematics 1.3 節）。2 進表記の最上位ビットを末尾に回す操作に等しい。$n=1,2,5,8,16,100$ で $O(N)$ 版と一致を実測。
よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| 0/1-indexed の混在で 1 ずれる | 漸化式は 0-indexed | 内部 0-indexed、出力直前で +1 |
| list.pop シミュレーションで TLE | 全体 $O(N^2)$ | 漸化式 $O(N)$ / 飛ばし $O(K\log N)$ |
| $O(K\log N)$ 版を $K\ge N$ でも使い RecursionError | k > n 分岐が深さ $N$ | $K$ の大きさで $O(N)$ ループに切り替え |
| res += res//(k-1) の条件を res <= 0 にする | res == 0 は周の先頭の生存者で伸びは 0、else 側で正しい | if res < 0 |
次のステップ
- 出典: Concrete Mathematics（Graham–Knuth–Patashnik）1.3 節「The Josephus Problem」。AtCoder では除去順ごと求める BIT 上の二分探索（Day 087・Day 135）型の出題が多い
- 発展: 「$m$ 番目に除去される人」への拡張（漸化式の拡張か BIT 上の $k$ 番目探索）
- 扱わなかった範囲: $100<K<N$ での最適切り替え点の実測、$O(K\log N)$ 版の非再帰化
- 次回予告: Boyer–Moore 多数決 + 区間多数派クエリ