最終更新: 2014-04-25T14:53+0900
迷路より簡単。右下から左上に向かって、右の要素と下の要素を参照しながら順番に処理するだけ。
matrix = DATA.lines.map{|ln| ln.chomp.split(",").map(&:to_i) } raise "正方行列でない!" if matrix.size != matrix[0].size (matrix.size-1).downto(0){|i| (matrix[i].size-1).downto(0){|j| incr = nil incr = matrix[i][j+1] if j+1 < matrix[i].size incr = matrix[i+1][j] if i+1 < matrix.size && (!incr || matrix[i+1][j] < incr) matrix[i][j] += incr if incr } } p matrix[0][0] __END__ content of matrix.txt here.
まだまだ簡単。最下段から、行を右へ左へ処理しながら上へ向かうだけ。こういう、問題・入力に依存して可変長のメモリを確保したりしない、そのうえ問題を単純に走査するだけの解法は安心できる。
Matrix = DATA.lines.map{|ln| ln.chomp.split(",").map(&:to_i) }.transpose # transpose:問いの右から左が、下から上への処理になる。 Order = Matrix.size raise "正方行列でない!" if Matrix.size != Matrix[0].size row = Matrix[0].dup # 1-line memo. row is now at the first(top) line of Matrix. 1.upto(Order-1){|i| # move from up ↓↓↓↓↓↓↓↓↓↓ 0.upto(Order-1){|j| row[j] += Matrix[i][j] } next if i == Order-1 # 最後の行は横移動不要(※禁止ではない)。最小値だけを選び取って答えにするから。 # move right →→→→→→→→→→ 0.upto(Order-2){|j| src, dst, move_cost = row[j], row[j+1], Matrix[i][j+1] row[j+1] = src + move_cost if src + move_cost < dst } # move left ←←←←←←←←←← (Order-1).downto(1){|j| src, dst, move_cost = row[j], row[j-1], Matrix[i][j-1] row[j-1] = src + move_cost if src + move_cost < dst } } p row.min __END__ content of matrix.txt here.
Array#transposeを使う機会があるなんて思わなかった!好きなメソッドは transpose(今日だけ)。ま、使わなくてもいいんだけど線形にアクセスするために。ま、メモリ構造からは遠く離れた Rubyなんだけど。
N×N確保していた作業メモを 1行分だけで済ませるようにスクリプトを修正。
コメントに「transpose:問いの右から左が、下から上への処理になる。」ってあるけど、今問題文を見ると左から右になってる。まあ、どっちからどっちでも変わらないからね。問題文が左から右になったからってわけではないけど、アップデート後は上から下の処理に変えてる。下から上だと、どうしてもその必然性を探してしまうから。
シリーズの締め。迷路のときとは違って 80×80ともなると手当たりしだいに探索の手を伸ばしていくと 10分以上の時間がかかる。優先度を付けると insertのコストが加わったにもかかわらず、笑っちゃうぐらい一瞬で終わった。
C++だったら queueの実装として std::multimapを使うところだけど配列をヒープ構造にするのもありだ。
Matrix = DATA.lines.map{|ln| ln.chomp.split(",").map(&:to_i).freeze }.freeze raise "正方行列でない!" if Matrix.size != Matrix[0].size matrix = Matrix.map{|ln| Array.new(ln.size) } size = matrix.size moved = lambda{|i,j, l,m| return false if not (0...size).include?(l) or not (0...size).include?(m) src, dst, move_cost = matrix[i][j], matrix[l][m], Matrix[l][m] return false if dst && dst < src + move_cost matrix[l][m] = src + move_cost return true } matrix[0][0] = Matrix[0][0] queue = [[0,0]] insert = lambda{|l,m| val = matrix[l][m] queue.insert(queue.index{|i,j| val <= matrix[i][j] }||queue.size, [l,m]) } until queue.empty? i,j = *(queue.shift) break if matrix.last.last and matrix.last.last <= matrix[i][j] [[i-1,j],[i+1,j],[i, j-1],[i,j+1]].each{|l,m| if moved[i,j, l,m] insert[l,m] end } end p matrix.last.last __END__ content of matrix.txt here.
<queue>ヘッダには priority_queueクラスがあるし、<algorithm>には make_heap
, pop_heap
, push_heap
といった、配列(RandomAccessIteratorをそなえたコンテナ)にかぶせて使うための関数があった。そりゃあるわなあ。ソートキーが要素のみから算出できない今回の場合に priority_queueを使う(外部キー)か、multimapを使う(内部キー)かはやっぱり決めかねるけど。