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

ゆらのふなびと

競プロ, Python, C++

SRM680 Div2 Med(500) BearChairs

競プロ シミュレーション

問題

I guess you have never seen a bear eating at a table. The reason is simple: bears don't use tables. However, they may sometimes decide to sit on a chair while eating.

Bear Limak is a waiter in a huge restaurant for bears. The restaurant has infinitely many chairs. The chairs are arranged in a single long row. In order, they are numbered using all positive integers: 1, 2, 3, ... Chair number 1 is closest to the entrance to the restaurant.

A bear takes a lot of space while eating, and all bears value their personal space. Limak knows that there is a universal constant d with the following meaning: Whenever two bears sit on chairs, their chair numbers must differ by d or more. For example, if d=10, you can have two bears in chairs 47 and 57, but you cannot have bears in chairs 47 and 56.

The restaurant just opened for the day and all chairs are empty. During the day exactly N guests arrived, one at a time. Whenever a guest arrived, Limak assigned them a chair. Each guest stayed in the restaurant in their assigned chair until the end of the day.

Generally, guests don't like to be seated close to the entrance because of the noise from the street. You are given a tuple (integer) atLeast with N elements: one for each guest, in order. For each i from 0 to N-1, guest i came with a request: "My chair number must be greater than or equal to atLeast[i]."

When seating a guest, Limak always assigns them the smallest available chair number. (That is, the smallest chair number that matches the guest's request and is at least d away from each of the bears who are already in the restaurant.) Return a tuple (integer) with N elements: for each guest, in the order in which they arrived, the number of the chair where they will be seated.

  • レストランに順番にN人の客がやってくる*1
  • 席には 1, 2, 3,... と正の整数の番号が振られており,客iはatLeast[i]以上の番号の席に座りたがっている.
  • また,全員に共通したパラメータとしてパーソナルスペースd(正整数)があり,すべての客は互いに番号がd以上離れた席に座らなければならない.
  • 以上の条件を満たしつつ,すべての客にそれぞれできるだけ小さい番号の席を割り振ったとき,それぞれの客がどの席に座っているか答えよ.

解法

答えを記録するリスト(ans)の他に,使われている席を番号の小さい順に並べたもの(used)が必要になる.なぜなら客はできるだけ小さい番号に割り当てられるからだ.

このansとusedを用いて,以下のように処理を進める.

ポイントは,xを「その時点で客iが座れる最小の席番号」として更新しながら用いていることである.

  1. 初期化: ans[0] = used[0] = atLeast[0] (最初の客は希望の席に座れる)
  2. 客iに対してx = atLeast[i]とし,以下を繰り返す.
    1. x <= used[j] - d ならば,客iはxに座れる.そうでなければxをxとused[j] + dのうち大きな方に更新.
    2. xがどのusedよりも大きければ,客xは2.1の処理が終わった後のxに座る.
class BearChairs:
    def findPositions(self, atLeast, d):
        N = len(atLeast)
        ans = [];   ans.append(atLeast[0]);
        used = [];  used.append(atLeast[0]);
        for i in range(1, N):
            x = atLeast[i]
            for j in range(i): #i == len(used)
                if x <= used[j] - d:
                    ans.append(x)
                    used.insert(j, x)
                    break
                else:
                    x = max(x, used[j] + d)
            else:
                ans.append(x)
                used.append(x)
        
        return tuple(ans)

使われている席の順序を知る必要があることはわかっていたが,「なんだろう,プライオリティーキュー?」とか無駄に難しいことを考えてしまった.

簡単な方法でいいのでとりあえず実装してみるの大事(TLEしてから直せばいい,くらいのスタンス.今は.)

あとはシミュレーション問題で流れをちゃんと追えるようにすること.

*1:問題では熊なので「N体」というのが正しいかもしれないが,ここでは便宜上「N人」とさせていただく.