[AOJ] No. 0301 Baton Relay Game

問題

方針

配列を使って要素を削除していく方法は 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\) となります。

コード

提出したコード

シミュレーション