AtCoder Grand Contest 013 C 「Ants on a Circle」

問題文

C - Ants on a Circle

 

蟻を区別しないなら、蟻は他の蟻とぶつかってもそのまま進んでいくとしていい、という有名な話がある。そこで、まず蟻を区別しないとして、最終的に蟻がいる場所を求める。現時点ではどの場所の蟻が何番の蟻なのかわからないのでこれを決定したい。

まず、他の蟻とぶつかったら向きを反転するので、隣にいる蟻を追い越すことは絶対に無く、必ず1番からN番までの蟻が時計回りに並んでいることがわかる。よって、どの場所の蟻が何番なのかが1箇所でもわかれば残りは決定することが出来る。

ここで、蟻が他の蟻とぶつかるたびに向きを反転する、というのはややこしいので、やはり蟻は他の蟻とぶつかっても気にせず進むことにし、そのかわり番号を交換することにしよう。すると、はじめ1番だった蟻が最終的に何番になっているのかが求まればいいということになる。

常に時計回りに1番からN番までの蟻が並んでいることを思い出すと、時計回りに動いている蟻は他の蟻とぶつかるたびに自分の番号が1増え(Nの次は1とする)、反時計回りに動いている蟻は他の蟻とぶつかるたびに自分の番号が1減る(1の次はNとする)ということがわかる。1番の蟻が時刻Tまでに何回他の蟻とぶつかるかは計算できるので、はじめ1番だった蟻が最終的に何番になっているかがわかる。