概要

「円形に並んだ生存者の中で、毎回“現在位置から \(D_i\) 番目”を高速に見つけ、現在の子を削除する」問題です。
要点は、削除ありの順序統計（\(k\) 番目の要素検索）を高速に処理することです。

考察

この問題をそのままシミュレーションすると、各パスごとに「次の生き残りを順に数える」必要があります。
しかし \(N \le 2\times 10^5\) なので、毎回線形に探すと最悪で \(O(NM)\) となり間に合いません。

重要な観察 1: 数える対象は「現在の子 \(x\) を除いた生存者」

\(i\) 回目のパス開始時、生存者数を alive = N - i とすると、候補人数は
\(\text{others} = \text{alive} - 1\)
です（\(x\) は除外）。

\(D_i\) は非常に大きい（最大 \(10^9\)）ので、そのまま数える必要はなく、 $\( k = (D_i - 1) \bmod \text{others} + 1 \)\( とすれば、「実際に必要な \)1$〜others 番目」に圧縮できます。

重要な観察 2: 円環の「\(x\) の次から数える」は2区間に分けられる

番号順（1..N）で見ると、\(x\) の次から時計回りは

1. 区間 \([x+1, N]\)
2. その後に区間 \([1, x-1]\)

の順です（もちろん削除済みは飛ばす）。
したがって、 - まず \([x+1, N]\) にいる生存者数 cntAfterX を数える - \(k \le cntAfterX\) ならその区間内で \(k\) 番目 - そうでなければ k - cntAfterX 番目を先頭側（\([1, x-1]\) を含む全体先頭）から取る

という形で処理できます。

どう高速化するか

必要な操作は次の3つです。

• 位置 \(i\) の生存フラグを \(+1/-1\) 更新（削除）
• ある区間の生存者数取得（累積和）
• 生存者の中で「\(r\) 番目の番号」を取得（order statistics）

これは Fenwick Tree（BIT） で実現できます。
各位置に「生存なら1、退出なら0」を持たせることで、上記すべてが \(O(\log N)\) で可能です。

アルゴリズム

1. Fenwick Tree をサイズ \(N\) で作り、最初は全員生存なので全位置に 1 を入れる。
2. 現在ボール保持者 x = S。
3. 各パス \(i=0..M-1\) について:
   • alive = N - i
   • others = alive - 1
   • \(k = (D_i - 1)\bmod others + 1\)
   • cntAfterX = sum(x+1..N) を取得
   • 次の受け取り手 target を求める:
     • k <= cntAfterX のとき
       rank = sum(1..x) + k（生存者の通し順位）
       target = kth(rank)
     • それ以外のとき
       rem = k - cntAfterX
target = kth(rem)
   • 現在の x を退出させる（add(x, -1)）
   • x = target に更新
4. 最後の x を出力。

kth(r) は「Fenwick 木上の二分探索」により、生存者の累積和が初めて \(r\) 以上になる最小 index を返します。

計算量

• 時間計算量: \(O((N+M)\log N)\)
  （初期化 \(N\) 回更新 + 各パスで定数回の Fenwick 操作）
• 空間計算量: \(O(N)\)

実装のポイント

• D_i は大きいので long long で受ける（剰余計算後は int で可）。

• others は常に 1 以上（\(M \le N-1\) のため）なので 0 除算は起きない。

• Fenwick は 1-indexed で実装すると kth が書きやすい。

• このコードでは「受け取り手を決めてから現在の x を削除」しており、問題文の手順（渡した直後に抜ける）と一致しています。

  ソースコード

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

struct Fenwick {
    int n;
    vector<int> bit;
    Fenwick(int n = 0) { init(n); }
    void init(int n_) {
        n = n_;
        bit.assign(n + 1, 0);
    }
    void add(int i, int v) {
        for (; i <= n; i += i & -i) bit[i] += v;
    }
    int sumPrefix(int i) const {
        int s = 0;
        for (; i > 0; i -= i & -i) s += bit[i];
        return s;
    }
    int sumRange(int l, int r) const {
        if (l > r) return 0;
        return sumPrefix(r) - sumPrefix(l - 1);
    }
    int kth(int k) const { // 1-indexed k
        int idx = 0;
        int pw = 1;
        while ((pw << 1) <= n) pw <<= 1;
        for (int d = pw; d > 0; d >>= 1) {
            int nxt = idx + d;
            if (nxt <= n && bit[nxt] < k) {
                k -= bit[nxt];
                idx = nxt;
            }
        }
        return idx + 1;
    }
};

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

    int N, M, S;
    cin >> N >> M >> S;
    vector<long long> D(M);
    for (int i = 0; i < M; i++) cin >> D[i];

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

    int x = S;

    for (int i = 0; i < M; i++) {
        int alive = N - i;          // before removing x
        int others = alive - 1;     // candidates excluding x

        long long k = (D[i] - 1) % others + 1; // 1..others

        int cntAfterX = fw.sumRange(x + 1, N);
        int target;
        if (k <= cntAfterX) {
            int rank = fw.sumPrefix(x) + (int)k;
            target = fw.kth(rank);
        } else {
            int rem = (int)(k - cntAfterX);
            target = fw.kth(rem);
        }

        fw.add(x, -1); // x leaves
        x = target;    // ball holder for next pass
    }

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

---

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