はまやんはまやんはまやん

hamayanhamayan's blog

バトンリレーゲーム [パソコン甲子園2014 予選 G]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0301?year=2014

前提知識

考察過程

1. 制約として、aが小さいのが気になる
2. Maを考えると10^5*10^2=10^7なので簡単な計算なら間に合いそう
3. 隣に渡していって、1つ削除ができる…
4. 双方向リストで実現できる

解法

https://onlinejudge.u-aizu.ac.jp/status/users/hamayanhamayan/submissions/1/0301/judge/3157915/C++14

双方向リストを作ろう。
L[i] := iの左側(反時計回り)の数
R[i] := iの右側(時計回り)の数
bat := 現在バトンを持っている人
これを修正しながらシミュレートしていく。
最後にバトンを持っている人がbat、左側の人がl、右側の人がrだとする。
すると、R[l] = r, L[r] = lとすると、batが消える。
次にバトンを持つのは右側なのでbat=rとなる。
このときに答えも更新しておこう。
ans[i] := i番目の人の掃除が免除されているか

int N, M, Q;
int L[201010], R[201010];
int ans[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> Q;

    rep(i, 0, N) L[i] = i - 1, R[i] = i + 1;
    L[0] = N - 1;
    R[N - 1] = 0;

    rep(i, 0, N) ans[i] = 1;

    int bat = 0;
    rep(_, 0, M) {
        int a; cin >> a;
        if (a % 2 == 0) {
            rep(i, 0, a) bat = R[bat];
        } else {
            rep(i, 0, a) bat = L[bat];
        }

        ans[bat] = 0;
        int l = L[bat];
        int r = R[bat];
        R[l] = r;
        L[r] = l;
        bat = r;
    }

    rep(_, 0, Q) {
        int q; cin >> q;
        printf("%d\n", ans[q]);
    }
}