TopCoder SRM 680 (Div. 2) Medium. BearChairs

※エスパーで問題を理解したので本来の問題と若干違うかもしれません。

このレストランには一直線上に椅子が並んでいる。客 1 , ... , n が順番にやってきて、i 番目の客は atLeast[i] 番目以降の椅子に座らせなければならない。また客同士の距離は d 以上でなければならない。

最終的にそれぞれの客は何番目の座席に座っているだろうか。

愚直にシミュレートすればいい。

i 番目の客の位置をとりあえず x = atLeast[i] とする。もし x と他の客との距離が d 以上あるのであれば x に確定する。

一方、 x との距離が d 未満であるような客が存在するなら x を右にずらす必要がある。この作業を高速に行うために、d 未満であるような客のうち最も左に座っている客 y を探し出す。そのあと条件を満たすまで右に動かし続ける。

例えば x が次のような位置だったとしよう。このときは x を 1 番の覆う区間のすぐ右にずらせばいい。

しかし今度は 2 番と重なってしまった。そのため、x を 2 番の覆う区間のすぐ右にずらす。

3 番とは重ならないのでここに座らせればいい。

区間幅が同じなので、右にずらしたとき重なる可能性がある人は、いま重なっている人のすぐ右にいる人である。このことを使うと、座席の座標を昇順に持って while を回すだけでシミュレートできる。

Div2 の問題を解いたことがほとんどないので、これからは Div2 も目を通すことにした。