概要

円形に並んだ \(N\) 人の子供が順にボールをパスし、パスした子供は抜けていくシミュレーション問題。BIT（Binary Indexed Tree）を用いて、残っている子供の中から \(k\) 番目を高速に求める。

考察

素朴なアプローチの問題点

単純にリストや配列で円陣を管理し、1人ずつ数えていく方法では、\(D_i\) が最大 \(10^9\) と非常に大きいため、1つずつカウントすると TLE になります。

重要な気づき

1. 剰余による高速化: 残っている子供が \(R\) 人（ボール保持者を除く）のとき、\(D_i\) 人目を数えるのは円を何周もする可能性がありますが、実質的には \((D_i - 1) \mod R + 1\) 番目と同じです。これで数える人数を \(R\) 以下に抑えられます。

2. 「\(k\) 番目に残っている子供を見つける」問題: 円陣から抜けた子供を飛ばして数える操作は、「現在残っている子供の中で、ある位置から時計回りに \(k\) 番目の子供は誰か？」という問題に帰着できます。

3. BIT で \(k\) 番目を求める: BIT に各子供の存在（1 or 0）を格納すると、累積和で「位置 \(i\) 以下に何人残っているか」が分かります。さらに、BIT 上の二分探索（find_kth）で「全体で \(k\) 番目に残っている子供の番号」を \(O(\log N)\) で求められます。

アルゴリズム

1. BIT を初期化し、全位置に 1 をセット（全員が円陣に参加）。
2. 各パスについて以下を行う：
   • 残り人数 \(R = N - i - 1\)（現在のボール保持者を除く）で \(D_i\) の剰余を取り、実効的な距離 effective_d を計算。
   • 現在の位置 current より後ろ（番号が大きい側）に残っている子供の人数 after を求める。
   • effective_d <= after なら、current より後ろの中で effective_d 番目を探す。具体的には、全体での累積順位 bit.query(current) + effective_d 番目の子供を find_kth で求める。
   • そうでなければ、先頭に戻って effective_d - after 番目の子供を探す。
3. current を BIT から削除（値を -1 に更新）し、ボール保持者を更新。
4. \(M\) 回終了後、current を出力。

具体例

\(N=5, S=3, D_1=7\) の場合： - 残り人数 \(R=4\)、effective_d \(= (7-1) \mod 4 + 1 = 3\) - 位置 3 から時計回りに 3 人目 → 4, 5, 1 と数えて 1 にパス - 位置 3 を削除

計算量

• 時間計算量: \(O((N + M) \log N)\)（初期化に \(O(N \log N)\)、各パスに \(O(\log N)\)）
• 空間計算量: \(O(N)\)

実装のポイント

• find_kth の実装: BIT 上で二分探索を行い、累積和が \(k\) 以上になる最小の位置を \(O(\log N)\) で求める。通常の二分探索 + query だと \(O(\log^2 N)\) になるが、BIT の内部構造を利用することで \(O(\log N)\) に削減。

• 円環の処理: 「current より後ろ」と「先頭から」の 2 つのケースに分けることで、円環上の巡回を線形配列上の操作に変換している。

• \(D_i\) のオーバーフロー: \(D_i\) が最大 \(10^9\) なので long long で受け取り、剰余計算を正しく行う。

  ソースコード

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

struct BIT {
    int n, log_n;
    vector<int> tree;
    BIT(int n) : n(n), tree(n + 1, 0) {
        log_n = 0;
        while ((1 << (log_n + 1)) <= n) log_n++;
    }
    void update(int i, int val) {
        for (; i <= n; i += i & (-i))
            tree[i] += val;
    }
    int query(int i) {
        int s = 0;
        for (; i > 0; i -= i & (-i))
            s += tree[i];
        return s;
    }
    int find_kth(int k) {
        int pos = 0;
        for (int pw = (1 << log_n); pw > 0; pw >>= 1) {
            if (pos + pw <= n && tree[pos + pw] < k) {
                pos += pw;
                k -= tree[pos];
            }
        }
        return pos + 1;
    }
};

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M, S;
    cin >> N >> M >> S;
    
    BIT bit(N);
    for (int i = 1; i <= N; i++)
        bit.update(i, 1);
    
    int current = S;
    for (int i = 0; i < M; i++) {
        long long D;
        cin >> D;
        
        long long remaining = N - i - 1; // countable children (excluding current holder)
        int effective_d = (int)(((D - 1) % remaining) + 1);
        
        // Count active children with index > current
        int after = bit.query(N) - bit.query(current);
        
        int target;
        if (effective_d <= after) {
            int rank = bit.query(current) + effective_d;
            target = bit.find_kth(rank);
        } else {
            int k = effective_d - after;
            target = bit.find_kth(k);
        }
        
        // Remove current from circle
        bit.update(current, -1);
        current = target;
    }
    
    cout << current << endl;
    return 0;
}

この解説は claude4.6opus-thinking によって生成されました。