オフラインリアルタイムどう書く E32 の実装例(ruby)


問題の名前 : きれいな四角
問題 : http://nabetani.sakura.ne.jp/hena/orde32rects/
実装リンク集 : https://qiita.com/Nabetani/items/bd16f3fa1d9e4d0d60ae

で。

# 実装

まあ実装を。今回は珍しくコメントたくさん書いた。

```ruby:ruby2.6
# frozen_string_literal: true

require "json"

# 線分。水平線なら level が y 座標。lo と hi が左端と右端。垂直線なら x座標、上端、下端。
Seg = Struct.new( :level, :lo, :hi )

# 矩形
Rect = Struct.new( :x, :y, :right, :bottom ) do
  # 水平な線分の配列
  def hsegs
    [Seg.new( y, x, right ), Seg.new( bottom, x, right ) ]
  end

  # 垂直な線分の配列
  def vsegs
    [Seg.new( x, y, bottom), Seg.new( right, y, bottom ) ]
  end

  # 面積
  def size
    (right-x)*(bottom-y)
  end

  # 引数がselfに完全に含まれている？
  def include?(c)
    x<=c.x && y<=c.y && c.right<=right && c.bottom<=bottom
  end

  # 引数がselfの外側にある？
  def no_connection?(c)
    c.right<=x || c.bottom<=y || right<=c.x || bottom<=c.y
  end

  # other のせいで self がきたない矩形になる？
  def partial_intersect?(other)
    ! no_connection?(other) && ! other.include?(self)
  end
end

# 解くためのクラス
class Solver
  def initialize( rects )
    @rects = rects
    @hsegs = rects.flat_map(&:hsegs).sort_by(&:values)
    @vsegs = rects.flat_map(&:vsegs).sort_by(&:values)
    @ys = @hsegs.map(&:level).uniq
    @xs = @vsegs.map(&:level).uniq
  end

  # 線分 s 上の点が全て segs のあつまりに含まれる？
  def seg_cover?(s, segs)
    non_covered = s.lo
    segs.select{ |e| e.level == s.level }.each do |e|
      non_covered = e.hi if e.lo<=non_covered && non_covered<e.hi
    end
    s.hi<=non_covered
  end

  # 引数はきれいな矩形？
  def clean?(c)
    return false if @rects.any?{ |rc| c.partial_intersect?(rc) }
    return false unless c.hsegs.all?{ |s| seg_cover?(s, @hsegs) }
    return false unless c.vsegs.all?{ |s| seg_cover?(s, @vsegs) }
    true
  end

  # きれいな矩形の配列を返す
  def cleans
    # 以下のループは計算量を減らせるが、サボっている
    @ys.combination(2).flat_map do |tb|
      t,b = tb.sort
      @xs.combination(2).flat_map do |lr|
        l,r = lr.sort
        c = Rect.new( l, t, r, b )
        clean?(c) ? [c] : []
      end
    end
  end
end

# 解く
def solve( src )
  rects = src.split("/").map{ |e| Rect.new(*e.chars.map{ |s| s.to_i(36) }) }
  Solver.new( rects ).cleans.map(&:size).sort.join(",")
end

if __FILE__==$PROGRAM_NAME
  if ARGV.size != 1
    puts "usage: #{__FILE__} data.json"
    exit
  end
  data = JSON.parse( File.open( ARGV[0], &:read), symbolize_names:true )
  data[:test_data].map{ |number:, src:, expected:|
    actual = solve( src )
    (expected==actual).tap do |ok|
      p [ (ok ? "ok" : "**NG**"), number, src, expected, actual ]
    end
  }.tap{ |r| puts( r.all? ? "everything is okay" : "something wrong" ) }
end
```

[Go による実装]( https://qiita.com/Nabetani/items/71701b5d7987cdb2b380 )とは異なる戦略。

# 実装戦略

順に説明すると：

1. 矩形から、垂直な線分と水平な線分を抽出する。
2. 水平な線分の y座標から2個選ぶ。
3. 垂直な線分の x座標から2個選ぶ。
4. (2)と(3)で選んだ4座標で矩形を作る
5. 作った矩形がきれいならリストに追加する

という感じ。(5) の「きれいなら」の部分が `Solver#clean?` に書かれている。このメソッドの戦略は下記の通り：

а. 他の矩形が邪魔をしない
б. 他の矩形によってちゃんと境界線が作られている

の両方が真なら「きれい」である。

(а) は `Rect#partial_intersect?` で書かれている。
(б) は `Solver#seg_cover?` で書かれている。

(б) について説明すると。

上辺、下辺 について、以下のように「ちゃんと境界線が作られている」か否かを調べる

壱. 「まだカバーされていない場所の左端」として、上辺または下辺（以下、辺）の左端を憶えておく。
弐. 辺と同じy座標の水平線を集める（以下、線分列と呼ぶ）
参. 線分列内の線分を列挙し、線分が「まだカバーされていない場所の左端」を含んでいたら、「まだカバーされていない場所の左端」を線分の右端に変更する
肆. 「まだカバーされていない場所の左端」が辺の右端以上に右になったら「ちゃんと境界線が作られている」

左辺、右辺 についても同様に調べる。

ここで重要なのは、 `Solver#initialize` で行われれている `sort_by(&:values)` 。整列済みなので線分を順に調べるだけで「ちゃんと境界線が作られている」か否かがわかる。

という具合。

# というわけで

ソースコードコメントに書いたとおり、`Solver#cleans` 内の 二重 `combination(2).flat_map` が遅い。このループを回すだけで、矩形の数を R として、$O\(R^4\)$ である。工夫の余地があるが、問題のサイズが小さいことがわかっているので工夫していない。

一方。地図を作っていないので、座標が百兆だったり浮動小数点数だったりしても問題ない。

トータルの計算量としては、矩形の数を R としたら $O\(R^5\)$ かな。

分量としては、コメントやら空行やらテストランナーを含んでぴったり百行。
地図を作る戦略よりも難しそうな印象で書き始めたけど、書いてみるとわりとシンプルになった。

会場でお見せしたときには `combination` のブロック引数の順序に依存していたが、指摘を受けてちゃんと `sort` した。