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 を回すだけでシミュレートできる。
TopCoder SRM 680 (Div. 2) Medium. BearChairs
Div2 の問題を解いたことがほとんどないので、これからは Div2 も目を通すことにした。