第22回オフラインリアルタイムどう書く 上と左の合計 の実装例と若干の解題

問題 : http://nabetani.sakura.ne.jp/hena/ord22irrpas/
解答リンク集 : http://qiita.com/Nabetani/items/34bf2a05099a47e193b6
イベント : http://yhpg.doorkeeper.jp/events/11378

当日お見せした実装。
ruby です。
参加者の感想を伺うと難しかったようです。

def find_cell( x, y, cells )
  cells.find{ |cell|
    cell[0]<=x && x-cell[0] < cell[2] && cell[1]<=y && y-cell[1] < cell[3]
  }
end

def value_impl(x, y, cells)
  return 0 if x<0 || y<0
  return 1 if x==0 && y==0
  c=find_cell( x, y, cells )
  return 1 if c && c[0]==0 && c[1]==0
  if c
    lefts = (c[0]...(c[0]+c[2])).map{ |xx|
      find_cell( xx, c[1]-1, cells ) || [ xx, c[1]-1, 1, 1, ]
    }
    tops = (c[1]...(c[1]+c[3])).map{ |yy|
      find_cell( c[0]-1, yy, cells ) || [ c[0]-1, yy, 1, 1 ]
    }
    (lefts+tops).uniq.map{ |cell |
      value( cell[0], cell[1], cells )
    }.inject(&:+)
  else
    value( x-1, y, cells ) + value( x, y-1, cells )
  end
end

def value(x, y, cells)
  @memo ||= {}
  @memo[ [x,y,cells].join("|") ] ||= value_impl( x, y, cells )
end

def solve( s )
  w,h=s.split(":").first.split("x").map(&:to_i)
  cells=s.split(":").last.split(",").map{ |x| x.chars.map(&:to_i) }
  "%02d" % ( value(w-1,h-1,cells) % 100 )
end

$stdout.sync=true
DATA.map do |line|
  num, src, exp = line.split(/\s+/)
  actual = solve( src )
  ok = actual==exp
  if ok
    puts( "ok : %s" % src )
  else
    puts( "%d %s\n   A:%s\n   E:%s\n" % [ num, src, actual.inspect, exp.inspect ] )
  end
  ok
end.all?{ |x| x }.tap{ |x| puts( x ? "Okay!" : "**NG**" ) }

__END__
0 8x6:6214,3024,5213,5022,0223,7115 32  
1 1x1:  01  
2 2x3:  03  
3 9x7:  03  
4 2x3:0021  03  
5 2x3:1012  03  
6 2x3:0022  02  
7 9x9:1177  98  
8 7x7:2354  02   

いつも通り、テストデータの大半は省略。

出題者としては、メモ化つき再帰 一択 という気分だったんだけど、当日メモ化つき再帰で来た方はおらず、意外だった。

上記のコードの肝を擬似コードで書くと

value_at(cell){
  return 0 if ( cell の上端か左端のどちらかが負 )
  return 1 if ( cell が左上隅である )
  neibours := cell の 上隣と左隣のセル全部
  sum := 0
  foreach( neibour_cell in neibours ){
    sum += value_at(neibour_cell)
  }
  return sum
}

こんな感じ。

これだけだと膨大な時間がかかって処理が終わらないのでメモ化する。
上記の ruby で @memo と書いてある場所がそれ。

メモ化については
google:メモ化再帰
で探して下さい。