読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

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 番の覆う区間のすぐ右にずらせばいい。

f:id:pekempey:20160129162715p:plain

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

f:id:pekempey:20160129162725p:plain

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

f:id:pekempey:20160129162731p:plain

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

TopCoder SRM 680 (Div. 2) Medium. BearChairs

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