AOJ 0192 Multistory Parking Lot (Ruby)
僕は競技プログラミングは大したことがないけれど、印象に残っている解答を載せてみようと思います。
これは Aizu Online Judge (AOJ)の問題。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0192&lang=ja
コード。
class Car num = 1 define_method(:initialize) do |wait_time| @num = num num += 1 @time = wait_time end attr_reader :num attr_accessor :time define_singleton_method(:clear) {num = 1} end class ParkingLot Space = Struct.new(:upper, :lower) def initialize(num) @spaces = num.times.map {|i| Space.new} end def add_car(wait_time) idx = @spaces.index {|sp| sp.lower.nil?} if idx @spaces[idx].lower = Car.new(wait_time) #下のスペースが空いている else return false if @spaces.all?(&:upper) #満車 #下は空いていないが満車でない場合 idxs = @spaces.map.with_index {|sp, i| sp.upper ? nil : i}.compact idx = idxs.map {|i| diff = @spaces[i].lower.time - wait_time diff >= 0 ? [diff, i] : nil }.compact.sort.first&.last unless idx idx = idxs.map {|i| [wait_time - @spaces[i].lower.time, i]} .sort.first.last end @spaces[idx].upper = @spaces[idx].lower @spaces[idx].lower = Car.new(wait_time) end true end def next @spaces.each do |sp| if sp.lower sp.lower.time -= 1 sp.upper.time -= 1 if sp.upper end end out = [] 2.times do @spaces.each do |sp| if sp.lower && sp.lower.time <= 0 out << sp.lower.num sp.lower = sp.upper sp.upper = nil end end end out end #車庫が空か def empty? @spaces.all? {|sp| sp.lower.nil?} end end until (given = gets.split.map(&:to_i)) == [0, 0] m, n = given parking_time = n.times.map {gets.to_i} pl = ParkingLot.new(m) result = [] entrance = [] Car.clear t = 0 loop do result += pl.next entrance << parking_time.shift if (t % 10).zero? while (wait_time = entrance.shift) unless pl.add_car(wait_time) entrance.unshift(wait_time) #満車の場合 break end end break if pl.empty? t += 1 end puts result.join(" ") end
別に速くも短くもない解答だけれど、なかなか複雑な問題で、コードを自分なりに読みやすく書けたのが印象に残っています。0.05秒。
解説
問題が複雑なので、どう解説したものかな。
まず、車を表すCar
クラスと、駐車場を表すParkingLot
クラスを作りました。
Car クラス。
car = Car.new(wait_time)
で、駐車時間 wait_time の車を作る。car.time
で残りの駐車時間にアクセスできる。car.num
で車の整理番号がわかる。Car.clear
で、車の整理番号を最初に戻す。
ParkingLot クラス。
- 内部に駐車スペースを表す
ParkingLot::Space
クラスがあって、(sp = Space.new
として)sp.upper
、sp.lower
で、駐車スペースのそれぞれ上段、下段に入っている車を意味する。nil なら空いている。 pl = ParkingLot.new(m)
で、m
台の駐車スペースをもった駐車場を作る。- すべての駐車スペースは
@spaces[]
。 pl.add_car(wait_time)
で、駐車時間 wait_time の車を(満車でなければ)1台入庫させる。返り値が true のときは駐車できた、false のときは満車だったことを意味する。- 順番に、下段が空いていれば下段に入庫させる。
- 下段が空いていなければ、下段の車を上段に上げて、空いた下段に入庫させる。このときのルールは面倒だが(上段の車が出やすいようにしている)、頑張って処理する。
pl.next
ですべての車の残り時間を1分減らし、出庫できる車は出庫させる。返り値は配列で、出庫するすべての車の整理番号が入っている。- まず下段の出庫可能な車をすべて出し、出したもので上段に車があれば下段に下ろし、また下段の出庫可能な車をすべて出す。
pl.empty?
で、駐車スペースがすべて空になったか判定する。
最初は時刻t
= 0。車の整理番号を初期化する(Car.clear
)。
メインループ。
- 出庫できる車は出庫させる(
pl.next
)。 - 10分ごとに1台、車がやってくる。入り口で待たせる(その車の駐車時間を
entrance[]
に push する)。 - 満車になるまで、待っているすべての車を入庫させる(while ループ)。満車になったら入り口で待たせておく。
- 駐車スペースがすべて空になっていたら break で終了。
- 時間を1分進める。で、繰り返し。
終わったら結果result[]
を出力。
いやあ、面倒ですねえ。
あとから気づいた問題点
- メインループでは車を wait_time で表しているが、これはじつは残りの駐車時間なので、Car クラスのインスタンスで表した方がよい。
- それぞれの車の残りの駐車時間を減らすのをすべて ParkingLot クラスで処理しているけれど、Car クラスのメソッドにした方がよかった。
- 時間管理はそれぞれの車の残りの駐車時間
@time
と、全体の時刻t
の二つあるけれど、両者に関連がないので、統一した方がよかったか。しかしこれは、統一するのはちょっと面倒そう。TimeManage クラスとか作るとよいかも知れない。まあ、統一はいたずらに複雑になって、ここではオーバースペックな気もする。実際の駐車場管理プログラムを書くのなら、絶対に統一しないといけないだろうな。
以上を考慮に入れて、リファクタリングしました。
AOJ 0192: Multistory Parking Lot · GitHub