[AOJ] No. 0301 Baton Relay Game

2019年5月18日

問題

方針

配列を使って要素を削除していく方法は TLE となる可能性があるので、リング配列のポインタを考えます。

配列 \(prev \) の \( prev[i] \) を 番号 \( i \) の後ろの番号、配列 \(next\) の \( next[i] \) を 番号 \( i \) の前の番号とします。ここで、前とは、時計回りの方向とします。一回の宣言でバトンが回る回数は最大でも \( 100 \) 回なので、実際にシミュレーションを行います。

ここで、番号 \( p \) が抜けるとします。番号 \( v = prev[p] \) 、番号 \( u = next[p]\) とすると、\( next[v] = p\) と \( prev[u] = p \) となっているので、これを変えないといけません。 つまり、\( next[v] = u \)、\( prev[u] = v\) となります。

コード

提出したコード

シミュレーション

  int prev[N], next[N];
  int flag[N];
  for (int i = 0; i < N; i++) {
    flag[i] = 1;
    prev[i] = (i - 1 + N) % N;
    next[i] = (i + 1) % N;
  }
  int p = 0;
  for (int i = 0; i < M; i++) {
    if (a[i] % 2 == 0) {
      for (int j = 0; j < a[i]; j++) {
        p = next[p];
      }
    } else {
      for (int j = 0; j < a[i]; j++) {
        p = prev[p];
      }
    }
    flag[p] = 0;
    prev[next[p]] = prev[p];
    next[prev[p]] = next[p];
    p = next[p];
  }