C - Ants on a Circle
700点問題2問目も解説ACでした…
蟻本の由来になったとか？
典型なんでしょうか。全くわからなかったです。
問題：周の長さLの円にN匹の蟻がいる。蟻は単位時間に１進み、時計回り化反時計回りか最初に決まっている。蟻同士が出会うと２匹とも反転して進む向きを変える。時間Tが立った後それぞれの蟻はどこにいるか
解説：
まず弾性衝突と呼ぶらしいです。
確かに物質見ればそうですね。
弾性衝突では、お互いが入れ替わるとして考えてよいらしいので、N匹の蟻の位置はわかります。
このままではどの蟻がはじめどの番号だったかわかりません。
蟻の番号は入れ替わらないので、1~nの昇順で並んでいます。
ぶつかったとき、時計回りの蟻は番号が1増えて、反時計回りの蟻は番号が1減るとすればよいです。
1匹について愚直にシミュレートすると、1匹の位置からすべての蟻の番号が定まり解けました。
もし同じ座標に2匹いる状態なら、時計回りのほうが小さい番号、反時計回りのほうが大きい番号になるのでそうしましょう。
感想：
まず弾性衝突でのコツを知りませんでした。
そして、番号を求めるところでは結果だけ注目するという感じでしょうか。
弾性衝突ということを知ったあとは自力で解きたかったですね。
ぶつかる回数で番号の遷移がわかること、O(1)でぶつかる回数がわかることがポイントでした。
考察厳しいです。同じような考察できるようになる気がしません。
実装もまあまあ重めだったのでそのうちやり直そうと思います
