概要

円陣に残っている子供の中で、現在のボール保持者から \(D_i\) 番目の子供へボールを渡し、その後保持者が抜ける操作を \(M\) 回行います。

残っている子供を高速に管理し、「残っている子供のうち \(q\) 番目」を高速に求めるために、Fenwick Tree（BIT）を使います。

考察

現在円陣に残っている人数を \(k\)、ボールを持っている子供を \(x\) とします。

残っている子供たちを番号順、つまり時計回りの順に並べたとき、\(x\) がその中で \(rank\) 番目にいるとします。

例えば、残っている子供の番号が

\[ [1, 3, 4, 7, 8] \]

で、現在ボールを持っているのが \(4\) なら、\(4\) は \(3\) 番目なので \(rank = 3\) です。

このとき、\(x\) の次から時計回りに数える順番は、順位で見ると

\[ rank+1, rank+2, \ldots, k, 1, 2, \ldots, rank-1 \]

になります。

ただし、\(x\) 自身は数えないので、数えられる人数は \(k-1\) 人です。
そのため、\(D_i\) が非常に大きくても、実際には

\[ (D_i - 1) \bmod (k - 1) \]

だけ見れば十分です。

渡される相手の「残っている子供の中での順位」を \(q\) とすると、

\[ q = (rank + (D_i - 1) \bmod (k - 1)) \bmod k + 1 \]

で求められます。

あとは、この \(q\) 番目に残っている子供の番号を高速に求めればよいです。

素朴にリストで残っている子供を管理すると、削除や \(q\) 番目の探索に \(O(N)\) かかり、全体で \(O(NM)\) となってしまいます。
制約では \(N, M \leq 2 \times 10^5\) なので間に合いません。

そこで、Fenwick Tree を使って、

• ある子供が残っているかを \(1/0\) で管理する
• 子供が抜けたら \(1\) を \(0\) に更新する
• 残っている子供のうち \(q\) 番目を二分探索的に求める

ことを行います。

アルゴリズム

Fenwick Tree 上で、各子供について

• 残っているなら \(1\)
• 抜けているなら \(0\)

を管理します。

初期状態では全員残っているので、すべて \(1\) です。

変数として以下を持ちます。

• cur: 現在ボールを持っている子供の番号
• rank: cur が残っている子供の中で何番目か
• k: 現在残っている子供の人数

各パスについて、次の処理をします。

1. 次にボールを受け取る子供の順位 \(q\) を求める

$\( q = (rank + (D_i - 1) \bmod (k - 1)) \bmod k + 1 \)$

1. Fenwick Tree を使って、「残っている子供のうち \(q\) 番目」の番号を求める

2. 現在のボール保持者 cur を Fenwick Tree から削除する

3. 新しいボール保持者の順位 rank を更新する

削除前に、新しい保持者の順位が \(q\)、削除される現在の保持者の順位が rank です。

• \(q > rank\) の場合
  削除される子供が新しい保持者より前にいるので、新しい保持者の順位は \(1\) つ前にずれます。

  $\( rank = q - 1 \)$

• \(q < rank\) の場合
  削除される子供は新しい保持者より後ろにいるので、順位は変わりません。

  $\( rank = q \)$

なお、ボールは自分自身には渡されないので、\(q = rank\) にはなりません。

1. cur を新しい保持者に更新し、\(k\) を \(1\) 減らす

これを \(M\) 回繰り返し、最後の cur を出力します。

計算量

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

実装のポイント

Fenwick Tree では、累積和を使うことで「番号 \(i\) 以下に残っている子供の人数」を求められます。

さらに、Fenwick Tree 上で二分探索をすることで、「残っている子供のうち \(q\) 番目」を \(O(\log N)\) で求められます。

また、初期状態ではすべての子供が残っているので、Fenwick Tree は次のように初期化できます。

tree = [0] + [i & -i for i in range(1, N + 1)]

これは、すべての位置に \(1\) が入っている Fenwick Tree を直接作る方法です。

\(D_i\) は最大 \(10^9\) と大きいですが、実際に何周も数える必要はありません。
必ず

\[ (D_i - 1) \bmod (k - 1) \]

を使って、円周上の移動量を小さくして扱います。

ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    N, M, S = data[0], data[1], data[2]

    tree = [0] + [i & -i for i in range(1, N + 1)]
    high = 1 << (N.bit_length() - 1)

    cur = S
    rank = S
    k = N
    p = 3

    for _ in range(M):
        D = data[p]
        p += 1

        q = (rank + (D - 1) % (k - 1)) % k + 1

        idx = 0
        need = q
        step = high
        while step:
            nxt = idx + step
            if nxt <= N and tree[nxt] < need:
                idx = nxt
                need -= tree[nxt]
            step >>= 1
        next_cur = idx + 1

        j = cur
        while j <= N:
            tree[j] -= 1
            j += j & -j

        if q > rank:
            rank = q - 1
        else:
            rank = q

        cur = next_cur
        k -= 1

    print(cur)

if __name__ == "__main__":
    main()

---

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