概要

円陣に残っている子供だけを数えながらボールを渡し、渡した直後に元の持ち主が抜けていくゲームです。
「残っている子供の中で何番目か」を高速に管理することで解きます。

考察

各パスでは、現在ボールを持っている子供 \(x\) の次の子供から、円陣に残っている子供だけを数えます。

素朴に実際に \(D_i\) 人分進めると、\(D_i\) は最大 \(10^9\) なので間に合いません。
また、円陣を配列やリストで管理して毎回順に進めても、最悪で \(O(NM)\) になってしまいます。

重要なポイントは次の通りです。

• 円陣の順番は、番号 \(1,2,\ldots,N\) の順で固定
• 途中で子供が抜けるだけ
• 必要なのは「残っている子供の中で何番目か」という情報

そこで、残っている子供を \(1\)、抜けた子供を \(0\) として管理します。

現在残っている人数を \(\mathrm{alive}\) とします。
現在の子供 \(x\) 自身は数えないので、数える対象は \(\mathrm{alive}-1\) 人です。

そのため、\(D_i\) 番目に数える子供は、実際には

\[ k = (D_i - 1) \bmod (\mathrm{alive} - 1) + 1 \]

番目の子供と同じです。

例えば残っている人数が \(5\) 人で、自分以外の \(4\) 人を数える場合、
\(D_i=1,5,9,\ldots\) はすべて同じ子供を指します。

次に、現在の子供 \(x\) が残っている子供の中で前から \(r\) 番目だとします。
すると、時計回りに \(k\) 人進んだ先の子供は、残っている子供全体の中で

\[ ((r + k - 1) \bmod \mathrm{alive}) + 1 \]

番目になります。

この「残っている子供の中で \(t\) 番目の子供の番号」を高速に求めるために、Fenwick Tree を使います。

アルゴリズム

Fenwick Tree に、各子供について以下の値を持たせます。

• まだ円陣に残っているなら \(1\)
• すでに抜けたなら \(0\)

Fenwick Tree を使うと、次の操作が高速にできます。

• sum(x)
  番号 \(1\) から \(x\) までに残っている子供の人数を求める
  つまり、子供 \(x\) が残っている子供の中で何番目かを求められる

• kth(k)
  残っている子供の中で \(k\) 番目の子供の番号を求める

手順は以下の通りです。

1. 最初は全員残っているので、Fenwick Tree のすべての位置に \(1\) を入れる

2. 現在ボールを持っている子供を current = S とする

3. 各パスについて、次を行う

   1. 現在の残り人数を alive とする
   2. 実際に進む人数を

   $\( k = (D_i - 1) \bmod (\mathrm{alive} - 1) + 1 \)$

   とする 3. 現在の子供の順位を

   $\( r = \mathrm{sum}(\mathrm{current}) \)$

   で求める 4. 次にボールを受け取る子供の順位を

   $\( \mathrm{next\_rank} = ((r + k - 1) \bmod \mathrm{alive}) + 1 \)$

   として求める 5. kth(next_rank) により、実際の子供番号 next を求める 6. current の子供を Fenwick Tree から削除する 7. current = next とし、残り人数を \(1\) 減らす

4. 最後に current を出力する

計算量

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

実装のポイント

Fenwick Tree の kth(k) は、「累積和が初めて \(k\) 以上になる位置」を二分探索的に求める関数です。
これにより、残っている子供の中で \(k\) 番目の子供番号を \(O(\log N)\) で求められます。

また、\(D_i\) は最大 \(10^9\) と大きいため、計算には long long を使うと安全です。

各パスの時点では、まだ現在の子供 current は Fenwick Tree 上に残っています。
その状態で次の受け取り手を求め、その後で current を削除する点に注意します。

ソースコード

#include <bits/stdc++.h>
using namespace std;

struct Fenwick {
    int n;
    vector<int> bit;

    Fenwick(int n) : n(n), bit(n + 1, 0) {}

    void add(int idx, int val) {
        for (; idx <= n; idx += idx & -idx) bit[idx] += val;
    }

    int sum(int idx) const {
        int res = 0;
        for (; idx > 0; idx -= idx & -idx) res += bit[idx];
        return res;
    }

    int kth(int k) const {
        int idx = 0;
        int step = 1;
        while ((step << 1) <= n) step <<= 1;

        for (; step > 0; step >>= 1) {
            int nxt = idx + step;
            if (nxt <= n && bit[nxt] < k) {
                idx = nxt;
                k -= bit[nxt];
            }
        }
        return idx + 1;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, S;
    cin >> N >> M >> S;

    Fenwick fw(N);
    for (int i = 1; i <= N; i++) fw.add(i, 1);

    int current = S;
    int alive = N;

    for (int i = 0; i < M; i++) {
        long long D;
        cin >> D;

        long long k = (D - 1) % (alive - 1) + 1;
        int rank_current = fw.sum(current);

        int next_rank = (int)(((long long)rank_current + k - 1) % alive + 1);
        int next = fw.kth(next_rank);

        fw.add(current, -1);
        current = next;
        alive--;
    }

    cout << current << '\n';
    return 0;
}

---

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