問題 : 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:メモ化再帰
で探して下さい。