🚲
[ABC061 D] Score Attack
START〜GOAL間にない負閉路は無視する問題。
要点
- 負のコストを扱うのでベルマン-フォード法を用いる
例1のシミュレーション
| 周 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | ||||
| 1 | 4 | 7 | ||
| 2 | 収束したので終了する |
1-2-3 と進んで答えは 7 になる。
例2のシミュレーション
| 周 | 1 | 2 | |
|---|---|---|---|
| 0 | |||
| 1 | 2 | 1 | |
| 2 | 4 | 3 | 負閉路検出のため中止する |
頂点数回目も更新しているため inf となる。
ところが普通に書くと WA
N, M = gets.split.collect(&:to_i) # => [3, 3]
Edges = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2, 4], [2, 3, 3], [1, 3, 5]]
START = 1
GOAL = N
d = Hash.new(-Float::INFINITY)
d[START] = 0
success = catch(:abort) do
N.times do |i|
updated = false
Edges.each do |from, to, score|
v = d[from] + score
if v > d[to]
if i == N.pred
throw :abort
end
d[to] = v
updated = true
end
end
unless updated
break
end
end
true
end
ans = success ? d[GOAL] : "inf" # => 7
puts ans
何度見直しても間違いはないはずだが一部で WA になる。どうやら負閉路が GOAL に絡んでいないのに負閉路と判断するのがまずいらしい。それは具体的にどのようなケースだろうか？
負閉路がゴールに絡まないケース
| 周 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | |||||
| 1 | 0 | 1 | 1 | 0 | |
| 2 | 0 | 2 | 2 | 0 | |
| 3 | 0 | 3 | 3 | 0 | |
| 4 | 0 | 4 | 4 | 0 | 負閉路検出のため中止する |
たしかに、これを見れば見当違いの方向にある負閉路で START〜GOAL 間がループしてしまうと判断するのはおかしいとわかる。
コード (WA)
N, M = gets.split.collect(&:to_i) # => [4, 4]
Edges = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2, 0], [2, 3, 1], [3, 2, 0], [1, 4, 0]]
START = 1
GOAL = N
d = Hash.new(-Float::INFINITY)
d[START] = 0
success = catch(:abort) do
N.times do |i|
updated = false
Edges.each do |from, to, score|
v = d[from] + score
if v > d[to]
if i == N.pred
throw :abort
end
d[to] = v
updated = true
end
end
unless updated
break
end
end
true
end
ans = success ? d[GOAL] : "inf" # => "inf"
puts ans
修正後のコード (AC)
260 ms
N, M = gets.split.collect(&:to_i) # => [4, 4]
Edges = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2, 0], [2, 3, 1], [3, 2, 0], [1, 4, 0]]
START = 1 # => 1
GOAL = N # => 4
d = Hash.new(-Float::INFINITY) # distance
d[START] = 0
(N * 2).pred.times do |i|
updated = false
Edges.each do |from, to, score|
v = d[from] + score
if v > d[to]
if i == N.pred
v = Float::INFINITY # 関連する経路だけに(本当の値ではなく)∞を伝搬する
end
d[to] = v
updated = true
end
end
unless updated
break
end
end
d # => {1=>0, 2=>Infinity, 3=>Infinity, 4=>0}
ans = d[GOAL].infinite? ? "inf" : d[GOAL] # => 0
puts ans
| 周 | 更新 |
|---|---|
| 1 | 通常計算 |
| 2 | ↓ |
| 3 | ↓ |
| 4 | N(4)回目で更新があれば負閉路検知のため∞の伝搬を開始する |
| 5 | ↓ |
| 6 | ↓ |
| 7 | ↓∞の伝搬終了 |
負閉路検知で∞を伝搬させれば 2, 3 だけが∞になり 1, 4 に影響が出ていないのがわかる。
関係ない経路を除去する解き方
コード (196 ms)
N, M = gets.split.collect(&:to_i) # => [4, 4]
Edges = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2, 0], [2, 3, 1], [3, 2, 0], [1, 4, 0]]
START = 1 # => 1
GOAL = N # => 4
# スタートとゴールからたどりつけない辺を除外するか？
if true
def dfs(edges, from, visited = {})
unless visited[from]
visited[from] = true
edges[from].each { |to| dfs(edges, to, visited) }
end
visited
end
# スタートから辿りつけない辺を除外する
if true
start_to_goal = Hash.new { |h, k| h[k] = [] }
Edges.each { |a, b| start_to_goal[a] << b }
visited = dfs(start_to_goal, START) # => {1=>true, 2=>true, 3=>true, 4=>true}
Edges = Edges.find_all { |from, to, _| visited[from] && visited[to] }
end
# ゴールから辿りつけない辺を除外する
if true
goal_to_start = Hash.new { |h, k| h[k] = [] }
Edges.each { |a, b| goal_to_start[b] << a }
visited = dfs(goal_to_start, GOAL) # => {4=>true, 1=>true}
Edges = Edges.find_all { |from, to, _| visited[from] && visited[to] }
end
end
d = Hash.new(-Float::INFINITY) # distance
d[START] = 0
success = catch(:abort) do
N.times do |i|
updated = false
Edges.each do |from, to, score|
v = d[from] + score
if v > d[to]
if i == N.pred
throw :abort
end
d[to] = v
updated = true
end
end
unless updated
break
end
end
true
end
ans = success ? d[GOAL] : "inf" # => 0
puts ans
あらかじめ START と GOAL から行ける辺に絞ることで計算量を減らせる。また負閉路を検出した場合は START〜GOAL 間にあるのはわかっているので即停止して問題ない。
類題
Discussion