naoya_t@hatenablog

いわゆるチラシノウラであります

〈AGC埋め〉700点問題(AGC 013 C)

師走。
引き続きAGCの700点問題をちびちび埋めていく。

AtCoder Problems / AtCoder Scores が動かないと埋めが進まない…両サービスが精進に欠かすことのできないインフラになっている

12/1(土)

AGC 013 C - Ants on a Circle (700)

蟻本の蟻みたいな?
蟻を区別しないのであれば、時刻Tにどこに蟻がいるかは簡単に求められる。

でもこれはそういう問題じゃない…
蟻が衝突して反転するのを追跡しないといけない。

鉄道のダイヤグラムみたいなグラフを考えると
時計回り(CW)も反時計回り(CCW)も速度が秒速1なので、上りも下りも45度の斜めの線で、交差する箇所で向きを替えて進む感じか。

上りのみ or 下りのみしかない場合、スタート地点にTを足した(引いた)もの mod L が答え。

ダイヤグラムを45度回転させてみるとLLLのように階段状に降りていく感じで、
進める2つの方向は直交していて、下か右にしか進まないのでT秒で進む距離はマンハッタン距離でTになる。
1ブロックの幅はバラバラだけど、(下にnブロック右にnブロック)+下か右に1ブロック、みたいな感じで、このnは二分探索で求められる気がする。
どの角から始まるかは、最初の交点なので、そこまでの所要時間は(進行方向で最初に逆行するものまでの距離)÷2か。これも最初に逆行するものを見つけるのに二分探索。

二分探索のために、上りと下りに分類しておく。同じものを(+Lして)後ろにくっつけておくと距離の算出に便利かも。

時刻が1/2単位なので、2倍したもので整数演算して最後に÷2するといいかも。

計算量はO(Nlog max(N,T))かな。
→AC
https://beta.atcoder.jp/contests/agc013/submissions/3696927
時間めちゃかかったけど自力で一発ACは嬉しい。

解説読んだ

なるほど
蟻の背番号の並びは絶対に変わらない。回転はするけど。
1≦2≦3≦4≦...≦N
てことは、1つを追跡してどこに行くか分かればあとは(蟻を区別しないのであれば全ての蟻がどこに到着するか簡単に分かることを利用して)なんとかなる(のか?T秒後に隣りと衝突するやつを追ってしまっていた場合は?→後述)

交差しても曲がらず直進する斜めの線そのもの(蟻本の蟻)に番号をつけて、蟻がつけている番号つきゼッケンの交換回数を考える。
時計回り蟻が反時計回り蟻と交差するときは、必ず1つ大きい番号のゼッケンを受け取る。(ゼッケン番号=区間番号のようなもの。行ったり来たりするゼッケンというかたすきというか)
反時計回り蟻が時計回り蟻と交差するときは、逆に必ず1つ小さい番号のゼッケンを受け取る。
T秒間に何匹の逆回転蟻と交差するかはN×O(1)=O(N)で求めることができる。

ソートにO(NlogN)かかるから全体の計算量はO(NlogN)、ということで。

→AC
https://beta.atcoder.jp/contests/agc013/submissions/3697481

これ通すまでに3WAした…
原因は、
(1) 0番と同じ位置に来るやつがあったときの処理。向きの反転の逆算を難しく考えてた(というか何を考えるべきなのか間違えていた)。

T秒後に隣りと衝突するやつを追ってしまっていた場合は?
→時計回りで出発するやつは衝突後には番号の大きい方になっている。
→同様に、反時計回りで出発するやつは衝突後には番号の小さい方になっている。

(2)(intのオーバーフローみたいなありがちなやつではなく)距離d離れている逆向きの線と何回交差するかの計算が出来てなかったから。

(対面する方向での)距離がd、円周がL、時間がT秒のとき、当然ながら

  • T<dなら一度も出会わない
  • T=dなら一度出会う
  • d<T<d+Lなら一度出会う
  • T=d+Lなら二度出会う

といった感じになるはずなのだけれど、これを
1+(T-d)/L
で求めようとしていた。これではT<dのときにも1を返してしまう。

教訓:冗長になって構わないから自分が理解できるところまで分解しよう。常識的に想定するのではなく、入力の制約をちゃんと食わせよう。