AGC023-D:Go Home - 思考の墓場

こういう問題を解いていると競プロ楽しいなと思う(やはりパズルが好きなのでは？)。

問題

解法

　すべてのマンションが地点 $S$ から見て同じ方向にあるときは自明なので、そうでない場合を考える。
　初期状態から考えるとつらい気持ちになるので、終了状態から近い方から考えてみる。 $S$ から見て最も座標の小さい側にあるマンション $1$ の住人と、最も大きい側にあるマンション $N$ の住人だけが残った状態のバスは、今までのバスの軌跡によらず $P_1$ と $P_N$ の大小だけでバスの動きが決まる。仮に $P_1\gt P_N$ だとすると、マンション $N$ の住人はマンション $1$ の住人がバスを降りるまで、つまり一番最後までバス取り残されることになる(かわいそう)。そうなると、マンション $N$ の住人の目標は、マンション $1$ の住人にできるだけ早くバスを降りてもらうになるので、彼らの目標はマンション $1$ の住人と同じだと考えてよい。するとマンション $N$ のことはもう考えなくてよいから、マンション $1$ から $N-1$ までだと思って同様に考えればよい。このことを最初に述べた自明な形になるまで繰り返すことで、逆順でバスがどのように動くかを決めることができるので、この問題が解ける。時間計算量は $O(N)$ になる。