最終更新: 2011-09-17T21:10+0900
説明はできない。条件は二つで足りると思ったが間違いだったので三つにした。そうしたら通った。
require 'matrix'
AX, AY, BX, BY, CX, CY = 0,1,2,3,4,5
O = Vector[0,0]
count = 0
DATA.each_line{|ln|
nums = ln.chomp.split(',').map(&:to_i)
a, b, c = Vector[nums[AX],nums[AY]], Vector[nums[BX],nums[BY]], Vector[nums[CX],nums[CY]]
ab, ao, ac = b-a, O-a, c-a
bc, bo, ba = c-b, O-b, a-b
ca, co, cb = a-c, O-c, b-c
ab_cosOAB, ab_cosCAB = ao.inner_product(ab) / ao.r, ac.inner_product(ab) / ac.r
bc_cosOBC, bc_cosABC = bo.inner_product(bc) / bo.r, ba.inner_product(bc) / ba.r
ca_cosOCA, ca_cosBCA = co.inner_product(ca) / co.r, cb.inner_product(ca) / cb.r
count += 1 if ab_cosOAB >= ab_cosCAB and bc_cosOBC >= bc_cosABC and ca_cosOCA >= ca_cosBCA
}
p count
__END__
content of triangles.txt here.
一応の説明を試みると、三本の辺それぞれから見て、辺を構成しない頂点が原点より見上げる位置にあるどうかをコサインの大小で判定してる。ただ、コサインは X軸対称なので見上げてるのか見下ろしてるのかは実際のところわからない。だから二つの辺では不十分で、三つの辺すべてで判定しなければいけない。※この最後の文ではやっぱり説明できてない気がする。
検索した。外積なんて(言葉しか)知りません。問題文の「Cartesian plane」もわからなかったので無視したんだった。なんで Cartesianがデカルトになるの？
メソッド名を決めるまでで 9割が終わってる。
軽い辺から順番に有効にしていき、有効な辺のみで最初にすべての頂点を通ることができたとき、最後に有効にした辺、この辺は隣接する点のうち最も離れている二つを結ぶ最短経路。これより軽い辺を組み合わせてこの二点を結ぶことはできないし、これより重い辺を組み合わせて結ぶのは不必要な無駄を抱える。あとは、このように確定した辺の両端を一個の点とみなすようにしながら再帰的に確定していく。
def find_the_required_edge_with_maximum_weight(matrix)
active_edge = Hash.new{|h,k| h[k] = {} }
(0...matrix.size).map{|src|
((src+1)...matrix.size).reject{|dst| matrix[src][dst].nil? }.map{|dst|
[src,dst]
}
}.inject(&:+).sort_by{|src, dst| matrix[src][dst] }.each{|src, dst| # lighter edge first
active_edge[src][dst] = active_edge[dst][src] = true
visited = [false] * matrix.size
firstvisit = {src=>true, dst=>true}
until firstvisit.empty?
v = firstvisit.shift[0]
visited[v] = true
if visited.all?
return [src, dst]
end
active_edge[v].each{|nxt,|
firstvisit[nxt] = true unless visited[nxt]
}
end
}
return nil
end
matrix = DATA.lines.map{|ln| ln.chomp.split(",").map{|_| _ == '-' ? nil : _.to_i } }
sum_of_weight = matrix.map{|row| row.compact.inject(&:+) }.inject(&:+) / 2
reduced_sum_of_weight = 0
loop{
src, dst = *find_the_required_edge_with_maximum_weight(matrix)
weight = matrix[src][dst]
break if weight == 0
reduced_sum_of_weight += weight
matrix[src][dst] = matrix[dst][src] = 0
matrix.map!{|row| row.map!{|_| _ && weight < _ ? nil : _ } }
}
puts "#{sum_of_weight - reduced_sum_of_weight} saved. (#{sum_of_weight} -> #{reduced_sum_of_weight})"
__END__
content of network.txt here.
もう限界が近いのですよ。風呂の中でああでもないこうでもないと考えてやっと辿り着いたのが上の答え。sum_of_weightの割る 2は忘れるので注意。
Problem 107を検索した。→「最小全域木」「プリム法」「クラスカル法」
クラスカル法のつもりで書いたのが下。上のより 10倍速い。0.5秒が 0.05秒になるレベル。
matrix = DATA.lines.map{|ln| ln.chomp.split(",").map(&:to_i) }
sum_of_weight = matrix.map{|row| row.inject(&:+) }.inject(&:+) / 2
reduced_sum_of_weight = 0
trees = (0...matrix.size).map{|v| {v=>true} }
(0...matrix.size).map{|src|
((src+1)...matrix.size).reject{|dst| matrix[src][dst] == 0 }.map{|dst|
[src,dst]
}
}.inject(&:+).sort_by{|src, dst| matrix[src][dst] }.each{|src, dst| # lighter edge first
i_src, i_dst = trees.index{|tree| tree[src] }, trees.index{|tree| tree[dst] }
if i_src != i_dst
reduced_sum_of_weight += matrix[src][dst]
trees[[i_src, i_dst].min].update(trees[[i_src, i_dst].max])
trees.delete_at([i_src, i_dst].max)
break if trees.size == 1
end
}
puts "#{sum_of_weight - reduced_sum_of_weight} saved. (#{sum_of_weight} -> #{reduced_sum_of_weight})"
__END__
content of network.txt here.
ある段階で最短に見えた経路も木が育って起点が増えるにつれて最短でなくなることがある気がしたので、まわりくどい条件を課してたんだけど、いらん心配だったみたい。起点とか関係なしに軽い辺から繋いでるんだから、連結して起点が増えたところで、後から付け替える余地はなかった。
『[単行本] R. ブランデンベルク, P. グリッツマン【最短経路の本】 シュプリンガー・ジャパン株式会社』をもう一回読んでみよう。当時はグラフっていえば棒グラフ？ってな知識しかなかったからね。世界の秘密をひとつ覗いた気になったもんだ。ちなみに最近は非線形科学(類語：複雑系、自己組織化、創発、冪乗則)とかシステム生物学がブーム。