AGC013-C Ants on a Circle
30秒眺めただけで解けた。全力でイキっていきたい。
問題概要
長さ の円環上に蟻が
匹いて、ある向きを向いている。蟻は向いている向きに一定の速度で進んでいき、他の蟻とぶつかるとそれぞれ向きを変えて進み始める。
秒後にそれぞれの蟻がいる位置を求めよ。
解説
とりあえず、聖書を読んだことがあれば発想はすぐにできる。蟻の区別をなくせば、蟻どうしがそのまますり抜けたとみなすことができる。そのため、蟻の区別なしに 秒後にどこにいるかという情報は簡単にわかる。
次に、他の蟻とぶつかっても跳ね返ることから、蟻たちの相対的な位置関係はずっと変わらないので、並び順も変わらないことがわかる。これで、答えの候補が全部で 通りに絞れた。
ここで、円環であるがために割り当て方が 通り出てきてしまうので、これを特定したい。これは、
の地点を右側から/左側から何回蟻が通過するかカウントすれば簡単にできる。
ボトルネックは蟻の場所のソートになって、 でこの問題が解けた。
感想
本当に信じられないほど一瞬で解けた。うれしい。
