読者です 読者をやめる 読者になる 読者になる

アルゴリズム忘備録

競技プログラミングとかデータ分析とか

AtCoder Grand Contest 013 C - Ants on a Circle

agc013.contest.atcoder.jp

 

本番解けず。ありがぶつかるとき、方向を反転させるのではなく互いにすれ違い方向はそのまま直進と考えるのが定石の問題(参照:蟻本)

ただこの問題の場合、今仮想的に直進している「1番」の蟻(実際は反転を繰り返しているので1番ではない可能性がある)が何番なのかを計算する必要がある。

 

重要なのは以下の2点

・回転させれば1からNの順番は変わらない→つまり一匹の蟻だけ計算すればよい

・蟻が1回ぶつかるたびに番号が1増減する

本番中気づけなかったポイントは後者。つまり、1番の蟻をシミュレートして、反対方向に歩いてくるアリがT秒間でぶつかる回数を求めればよい。O(N)