概要

円陣に並んだ \(N\) 人の子供たちがボールを回し、パスを送った側が円陣から抜けていくゲームのシミュレーション問題です。パスの回数 \(M\) や移動距離 \(D_i\) が大きいため、単純なシミュレーションではなく、データ構造を用いた高速化が必要となります。

考察

素朴なシミュレーションの限界

リストや連結リストを使って「\(D_i\) 番目の人を探して削除する」という操作をそのまま実装すると、1回のパスに最悪 \(O(N)\) の時間がかかります。パスは \(M\) 回（最大 \(N-1\) 回）行われるため、全体の計算量は \(O(NM)\) となり、制約の \(N, M \le 2 \times 10^5\) では実行時間制限に間に合いません。また、\(D_i\) が最大 \(10^9\) と非常に大きいため、愚直に 1 人ずつ数えることも不可能です。

高速化の指針

この問題で必要な操作は以下の 2 点です。 1. 「現在円陣に残っている子供の中で \(k\) 番目の人は誰か」を高速に特定する。 2. 「子供が円陣から抜ける」という情報を高速に更新する。

これらを効率的に行うために、フェニック木（Binary Indexed Tree, BIT） を活用します。

ランクによる管理

円陣に残っている子供を \(1\)、抜けた子供を \(0\) として BIT で管理します。 - ある子供 \(i\) が、現在残っている子供たちの中で何番目（ランク）に位置するかは、BIT の \(1\) から \(i\) までの累積和 query(i) で求められます。 - 逆に、現在のランク \(k\) から子供の番号 \(i\) を特定するには、BIT 上で二分探索（または二分増幅）を行うことで \(O(\log N)\) で実行可能です。

移動の計算

現在のボール保持者のランクを \(r\)、残っている人数を \(K\) とします。 ボール保持者自身を除いた \(K-1\) 人の中から \(D_i\) 番目を数える際、実際に移動するステップ数は \(step = (D_i - 1) \pmod{K-1} + 1\) と簡略化できます。 - 現在のランク \(r\) から時計回りに \(step\) 進んだとき、 - \(r + step \le K\) ならば、次の保持者のランクは \(r + step\) です。 - \(r + step > K\) ならば、円を一周して戻るため、ランクは \(step - (K - r)\) となります。

アルゴリズム

1. 初期化: 長さ \(N\) の BIT を作成し、すべての要素を \(1\) にします。
2. パスのシミュレーション: \(M\) 回の各パスについて以下を行います。
   • 現在の人数 \(K\) を把握する（\(K = N - (\text{これまでに抜けた人数})\)）。
   • 現在の保持者 current_holder のランク \(r\) を BIT から取得する。
   • \(D_i\) を \(K-1\) で割った余りを利用して、次にボールを受け取る子供のランク target_rank を計算する。
   • BIT 上の二分探索で target_rank 番目の子供の番号 next_holder を特定する。
   • current_holder を円陣から抜く（BIT の current_holder 番目の値を \(0\) に更新する）。
   • 保持者を next_holder に更新する。
3. 出力: 最終的な current_holder を出力します。

計算量

• 時間計算量: \(O(M \log N)\)
  • BIT の更新と query に \(O(\log N)\) かかります。
  • find_kth（BIT 上の二分探索）に \(O(\log N)\) かかります。
  • これを \(M\) 回繰り返すため、全体の計算量は \(O(M \log N)\) となり、十分に高速です。
• 空間計算量: \(O(N)\)
  • BIT を管理するための配列に \(O(N)\) のメモリを使用します。

実装のポイント

• BIT 上の二分探索: find_kth 関数において、通常の二分探索（lower_bound）を使うと \(O(\log^2 N)\) になりますが、BIT の構造を利用した二分増幅（Binary Lifting）を用いることで \(O(\log N)\) で実装できます。

• 大きな \(D_i\) の処理: \(D_i\) は非常に大きくなる可能性があるため、必ず long long 型で受け取り、現在の有効人数 \(K-1\) で剰余をとる必要があります。

• 1-based indexing: BIT は通常 1 番目から管理するため、子供の番号 \(1 \dots N\) とそのまま対応させることができ、実装がスムーズになります。

  ソースコード

#include <iostream>
#include <vector>

using namespace std;

/**
 * FenwickTree (Binary Indexed Tree)
 * 競技プログラミングにおいて、要素の更新と累積和の取得をそれぞれ O(log N) で行うデータ構造です。
 * ここでは円陣に残っている子供の人数を管理するために使用します。
 */
template <typename T>
struct FenwickTree {
    int n;
    vector<T> tree;

    FenwickTree(int n) : n(n), tree(n + 1, 0) {}

    // i番目の要素にxを加算する
    void add(int i, T x) {
        for (; i <= n; i += i & -i) {
            tree[i] += x;
        }
    }

    // 1番目からi番目までの要素の合計を返す
    T query(int i) {
        T res = 0;
        for (; i > 0; i -= i & -i) {
            res += tree[i];
        }
        return res;
    }

    // 累積和がk以上となる最小のインデックスを O(log N) で見つける
    // これにより「現在残っている子供の中でk番目の子供」を高速に特定できます
    int find_kth(T k) {
        int idx = 0;
        int max_pow = 1;
        while (max_pow * 2 <= n) max_pow *= 2;
        for (int i = max_pow; i > 0; i >>= 1) {
            if (idx + i <= n && tree[idx + i] < k) {
                idx += i;
                k -= tree[idx];
            }
        }
        return idx + 1;
    }
};

int main() {
    // 入出力の高速化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, S;
    if (!(cin >> N >> M >> S)) return 0;

    // 最初はすべての子供（1からN）が円陣にいます
    FenwickTree<int> ft(N);
    for (int i = 1; i <= N; ++i) {
        ft.add(i, 1);
    }

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

        // 現在円陣に残っている子供の総数
        int K = N - i;
        
        // 現在ボールを持っている子供の、残っている子供たちの中での順番（ランク）
        int r = ft.query(current_holder);
        
        // ボールを持っている子供を除いた残りの子供の数は K-1
        // その中を時計回りに D 番目数える操作は、(D-1) % (K-1) + 1 番目と同じ
        long long step = (D - 1) % (K - 1) + 1;
        
        int target_rank;
        // 現在のランク r から時計回りに step 進んだときのランクを計算
        if ((long long)r + step <= (long long)K) {
            // 円の末尾（番号N）を超えない場合
            target_rank = (int)((long long)r + step);
        } else {
            // 円を一周して戻る場合
            target_rank = (int)(step - (long long)(K - r));
        }

        // 次にボールを受け取る子供の番号を特定
        int next_holder = ft.find_kth(target_rank);
        
        // ボールを渡した直後、元の持ち主は円陣から抜ける
        ft.add(current_holder, -1);
        
        // ボールが渡される
        current_holder = next_holder;
    }

    // M回のパス終了後にボールを持っている子供の番号を出力
    cout << current_holder << endl;

    return 0;
}

---

この解説は gemini-3-flash-thinking によって生成されました。