hirax.net::Keywords::「国際情報オリンピック」のブログ

■数学（コーディング）パズル、大好き!?　

　ここのところ、数学パズル||コーディング・パズルにハマっています。きっかけは、国際情報オリンピック（International Olympiad in Informatics）の予選問題にもなったことがあるという「入門レベルの問題」で、「200個以内の長方形の上左および右下座標(32bit floatで表現できるような実数)が与えられる。長方形は相互に重なりが許されるとき、与えられた長方形群により覆われた部分の面積を求めるコードを書け。今すぐ書け。あっ、実行時間が２秒を越えるようなコードはダメだかんね」というお題でした。

　あなたなら、このお題に対して、どんなコードを書くでしょう？VisualBasicでも、Perlでも、C++でも、Lispでも・・・、自分の言葉で問題を書き綴り・解き明かす「数学（コーディング）パズル」はっても楽しくスリリングなことなのだろう、と思います。きっと、それは固くなりがちな頭を柔らかくし、何らかの瞬発力を与えてくれるものであるような気がします。

　ちなみに、そのお題を与えられたとき、適当にRubyで書いたコードが下のものになります。あなたなら、どんなコードを書きますか？

def makeRect(n)
  data=[]
  n.times{ data＜＜[rand(),rand(),rand(),rand()] }
  return data
end

def makeMesh(rects)
  xg=[]
  yg=[]
  rects.each do |xt,xb,yt,yb|
    xg＜＜xt＜＜xb
    yg＜＜yt＜＜xb
  end
  xg.sort!
  yg.sort!
  mesh=[]
  (xg.length-1).times do |x|
    (yg.length-1).times do |y|
      cx=(xg[x]+xg[x+1])/2
      cy=(yg[y]+yg[y+1])/2
      area=(xg[x+1]-xg[x])*(yg[y+1]-yg[y])
      mesh＜＜[cx,cy,area] if area＞0
    end
  end
  return mesh
end

rects=makeRect(200)  
mesh=makeMesh(rects)
area=0 
mesh.each do |x,y,a| 
  rects.each do |xt,xb,yt,yb|
    if xt＜x&&x＜xb&&yt＜y&&y＜yb
      area+=a
      break
    end      
  end	
end
puts area