Google Code Jam 2010 Round 3

C

直線状にお店を配置することを考える。現在の座標とその位置に置ける店舗数が与えられるので、同じ場所にある二つの店舗について一つを左に、もう一つを右に移動させる、という処理を繰り返すことで、どの座標にも高々一つしかないようにしたい。このときの最小ステップ数を答えよ、という問題。(最初に与えられる座標は200個までで、店舗数の合計は100000個まで。)

検証はしていないけれど、最小ステップ数も最大ステップ数もないというか、どうやっても最終的に同じ結果になるはず。

ある地点Cに複数の店舗がある状況で、二つの店舗の競合を回避するには、一つを店舗のない一番近い左側の点Lに、もう一つを店舗のない一番近い右側の点Rに移動させれば良い。この操作を行うには、(C-L)*(R-C)ステップかかり、LとRに移動した分、CとR-(C-L)の地点から1店舗ずつ減った状態になる。この処理は、常に競合を一つずつ回避するので、店舗数の数だけ繰り返せば必ず終了する。

この処理を高速に行うことを考えると、店舗のない区間を管理することが必要になる。基本的に店舗のない区間は初期配置から得られるのと、各ステップで店舗が減るR-(C-L)の地点くらいなので、このような領域は400個くらいになる。(一見するとR-(C-L)の地点がどんどん増えそうだが、すぐに消費される。消費されなくてもせいぜい初期店舗配置数である200個くらいしか増えない。)なので特に何も考えずに毎回全部調べても問題ない。更新作業の際に、これらの領域がソートされているようにだけ気を付ける。