/ 最近 .rdf 追記 編集 設定 本棚

脳log[20110325] Problem 81, 82, 83



2011年03月25日 (金) 見えないところでの思いやりが、本当の思いやりなのだと思う。「誰にでも見える思いやり」なんてのは、思いやりではないのではないだろうか。」 たぶん最近多い ACの CMについて。この CM、いいと思うけどなあ。行動を促してるんだと思う。思うだけではダメで行動に移さなければいけない。思いは見えないけど行動すればそれは誰にでも見える。それを思いやりと(そのCMでは)呼ぶんだと。見せる必要はないけど、見えても嘘にはならないんじゃない。(こういうことは書いてもわかり合えるとは思わないのでコメントしないでここに書いてる)。目立つのを嫌って行動できない日本人は多そう。考えすぎ。それも言い訳を。子供の時にたたき込まれてたら照れもなくできるんだろうとも思う。レディファーストとか。

最終更新: 2014-04-25T14:53+0900

[ProjectEuler] Problem 81, 82, 83

 Problem 81

迷路より簡単。右下から左上に向かって、右の要素と下の要素を参照しながら順番に処理するだけ。

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.

 Problem 82

まだまだ簡単。最下段から、行を右へ左へ処理しながら上へ向かうだけ。こういう、問題・入力に依存して可変長のメモリを確保したりしない、そのうえ問題を単純に走査するだけの解法は安心できる。

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なんだけど。


 @2013-05-11 アップデート

N×N確保していた作業メモを 1行分だけで済ませるようにスクリプトを修正。

コメントに「transpose:問いの右から左が、下から上への処理になる。」ってあるけど、今問題文を見ると左から右になってる。まあ、どっちからどっちでも変わらないからね。問題文が左から右になったからってわけではないけど、アップデート後は上から下の処理に変えてる。下から上だと、どうしてもその必然性を探してしまうから。

 Problem 83

シリーズの締め。迷路のときとは違って 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を使う(内部キー)かはやっぱり決めかねるけど。