オフラインリアルタイムどう書くE28の実装例 ( Ruby )
オフラインリアルタイムどう書くE28の問題「増築の果ての隣室」の実装例を、Ruby で。
問題 : http://nabetani.sakura.ne.jp/hena/orde28sqst/
実装リンク集 : https://qiita.com/Nabetani/items/4e3fac2746ca05a93165
イベント : https://yhpg.doorkeeper.jp/events/81346
めちゃ面白いイベントなのに参加者すくなくて寂しいので参加者募集です！！！次回のイベントももう公開済みなのでぜひ。
負けました。正確には時間切れから発表中デバッグでバグを落としたけど計算量減らしてないのでNo30くらいまでしか通せず。家帰ってちょこちょこ直していまは通ってます。以下、ざっくり方針。
なんか計算で番号求められるんじゃね？って思ったんだけど、増築されていくごとに分割数が増えていくことにより、1辺の長さを割っていったもの(あるいはかけていったもの)が膨らんでいって、どうもさくっとは計算できなさそうだった。なので真面目に増築することにする。
Ruby なので有理数が扱えて最初の正方形の1辺を1としたときに4分割なら 1/4 、そのあと7分割なら 4/28 みたいな感じで考えていくと楽かも、と思った。ただどうも隣接の判定をミスりそうな気がしたので4分割したら最初の正方形の1辺を4、さらに7分割なら28と増やしていくことにした。Rubyなら扱いきれるだろ、みたいな雑な予想込みで。
んで、そうやってかけていった値をもとにすると、すべての部屋の辺の長さが整数で扱えるようになる。じゃあそのあとどうするのっていうと、 Hash{Integer => Hash{ Integer => Integer}} みたいな型で盤面を用意してほんとに正方形を塗っていくことにした。配列にしてないのはSあるいはW方向への増築をすると x, y がマイナス側にいくかもだから。全く塗る必要はないのだが脳内デバッグが下手すぎて実際に塗ってたらなんかわかるようになってきた。実際発表中に debug モードで見せたりしてウケた1。
ただこれがとんでもなく遅い。そりゃ当然だということで全部塗るわけじゃなくて辺だけ塗るようにした。
でもこれも遅い。辺すら塗る必要ないよね、といって部屋の情報を貯め込むようにした。
これもまた遅い。これがなんで遅いのかというと隣接判定のところで r1.to_a & r2.to_a 的なことをやってたせいだった。そりゃそうだ。隣接判定のため、x座標的にあるいはy座標的に同じところにいるかどうか、みたいな判定。
def neighbor?(other) if h_match?(other) x2 == other.x1 || x1 == other.x2 elsif v_match?(other) y2 == other.y1 || y1 == other.y2 end end def v_match?(other) !((x1...x2).to_a & (other.x1...other.x2).to_a).empty? end def h_match?(other) !((y1...y2).to_a & (other.y1...other.y2).to_a).empty? end
重なりがあること、というのがうまく言語化できなかったのだが両手をピースにしてごにょごにょ動かしてたら、一方の始点がもう一方の終点より大きいケースがだめであることがわかった。というわけで最終形は以下。これは普通に返ってくる。 x1, x2, y1, y2 の計算あたりは正方形なので全然いらない情報なのだが一旦通ってるのでこのままで。
class Solver Instruction = Struct.new(:dir, :size) Sq = Struct.new(:num, :x1, :x2, :y1, :y2) do def cover?(x, y) x1 <= x && x <= x2 && y1 <= y && y <= y2 end def neighbor?(other) if h_match?(other) x2 == other.x1 || x1 == other.x2 elsif v_match?(other) y2 == other.y1 || y1 == other.y2 end end def v_match?(other) !((x2 - 1) < other.x1 || (other.x2 - 1) < x1) end def h_match?(other) !((y2 - 1) < other.y1 || (other.y2 - 1) < y1) end end class Board attr_reader :min_w, :max_w, :min_h, :max_h def initialize @min_w = 0 @max_w = 0 @min_h = 0 @max_h = 0 @sqs = [] end def fetch(x, y) @sqs.find { |e| e.cover?(x, y) }&.num end def neighbors(num) t = @sqs.find { |e| e.num == num } @sqs.select { |e| t.neighbor?(e) }.sort_by(&:num) end def rect(num, x1, x2, y1, y2) @min_w = x1 if x1 < min_w @max_w = x2 if x2 > max_w @min_h = y1 if y1 < min_h @max_h = y2 if y2 > max_h @sqs << Sq.new(num, x1, x2, y1, y2) end end def initialize @base = 1 # base_size end def solve(input) a, b = input.split('/', 2) @target = b.to_i @insns = a.chars.each_slice(2).map do |s| Instruction.new(s[0].to_sym, s[1].to_i) end @insns.each do |insn| @base *= insn.size end board = Board.new board.rect(1, 0, @base, 0, @base) n = 1 @insns.each.with_index do |insn, i| minw = board.min_w maxw = board.max_w minh = board.min_h maxh = board.max_h case insn.dir when :N, :S tmp_base = (maxw - minw) / insn.size else tmp_base = (maxh - minh) / insn.size end 1.upto(insn.size) do |d| case insn.dir when :N x2 = minw + (tmp_base * d) x1 = x2 - tmp_base y1 = maxh y2 = maxh + tmp_base when :S x2 = minw + (tmp_base * d) x1 = x2 - tmp_base y2 = minh y1 = minh - tmp_base when :E y1 = maxh - (tmp_base * d) y2 = y1 + tmp_base x1 = maxw x2 = maxw + tmp_base when :W y1 = maxh - (tmp_base * d) y2 = y1 + tmp_base x2 = minw x1 = minw - tmp_base end board.rect(n+d, x1, x2, y1, y2) end n += insn.size end board.neighbors(@target).map(&:num).join(',') end end
