オフラインリアルタイムどう書く F02 の ruby による実装例

問題 : http://nabetani.sakura.ne.jp/hena/ordf02in2rec/
実装例リンク集 : http://qiita.com/Nabetani/items/109c31c265be7fa1a36c

まずは百万×百万だと死ぬ実装。

class Array
  def x; self[0]; end
  def y; self[1]; end
end

def cells_impl( rects )
  c=Hash.new{ |h,k| h[k]=0 }
  rects.each do |x0,y0,x1,y1|
    (x0..x1).each do |x|
      (y0..y1).each do |y|
        c[[x,y].join]+=1
      end
    end
  end
  c.keys.select{ |k| c[k]==2 }
end

def cells( src )
  cells_impl( src.split("/").map{ |rc| rc.scan(/\d+/).map(&:to_i) } )
end

def solve( src )
  cells( src ).size.to_s
end

DATA.map{ |line|
  num, src, expected = line.split(/\s+/)
  actual = solve( src )
  okay = actual == expected
  puts( "%s %s : %s->%s ( %s )" % [ (okay ? "ok" : "***NG***" ), num, src, actual, expected ] )
  okay
}.all?.tap{ |x| puts( x ? "okay!" : "something wrong" ) }
__END__
0 5,1-7,9/3,2-8,6/0,5-9,5 15
1 0,0-9,9/0,0-9,9/0,0-9,9 0

parse がやる気ない感じですいません。

すぐに数えないで cell のリストを作っているのは、出題の図を作るため。解くだけなら直接 count するのが良いと思う。

つづいて、百万×百万でも行ける実装

class Array
  def x; self[0]; end
  def y; self[1]; end
end

def solve_impl( src0 )
  src = src0.map{ |x| [[x[0], x[1]], [x[2]+1, x[3]+1]] }
  xs, ys = [:x,:y].map{ |m| src.map{ |rc| rc.map(&m) }.flatten.sort.uniq }
  r=0
  ys.each_cons(2) do |y0,y1|
    xs.each_cons(2) do |x0,x1|
      count = src.count{ |rc|
        rc[0].x<=x0 && x0<rc[1].x && rc[0].y<=y0 && y0<rc[1].y
      }
      next unless count==2
      r+=(y1-y0)*(x1-x0)
    end
  end
  r
end

def solve( src )
  solve_impl( src.split("/").map{ |rc| rc.scan(/\d+/).map(&:to_i) } ).to_s
end

DATA.map{ |line|
  num, src, expected = line.split(/\s+/)
  actual = solve( src )
  okay = actual == expected
  puts( "%s %s : %s->%s ( %s )" % [ (okay ? "ok" : "***NG***" ), num, src, actual, expected ] )
  okay
}.all?.tap{ |x| puts( x ? "okay!" : "something wrong" ) }
__END__
0 5,1-7,9/3,2-8,6/0,5-9,5 15
41  112863,136827-415321,945235/278661,676383-304033,860715/404074,160748-970146,761914 11439007625 

テストデータの大半は省略。

実装方針は二通りあると思う。
一方は上記のもの。座標圧縮っていうのかな。もう一方は
* https://twitter.com/angel_p_57/status/834338201657413632
* http://qiita.com/e0232/items/70f0a75daa97127bfdf5
* http://qiita.com/kota9/items/7fa5db61826bbf1fe3e5
にある戦略。

オフラインの現場で両方紹介できてラッキーだった。

なお。cielさんに指摘いただいたとおり、矩形の数が多いと死ぬ。2000個あると、一千万回以上ループが回ることになる。指摘されるまで気づかなかったのでちょっとくやしいけど、矩形が三個に固定という問題なのでこれでいい。

出題意図としては、とにかく平易な問題を作ろいうということに注力した。
10×10 の方は非常に簡単だったでしょ？

とはいえ、参加者を見るとあんまり簡単だと良くないかなと思い、百万×百万 も用意した。
百万×百万 の方はほどよい難易度になったと考えている。簡単すぎず、難しすぎず。