🌳
[ARC106 B] Values
パネポン風の操作を意識したグループ化問題。
1. 一致する場合
仮に A と B が次のようになっていて、
| 1 | 2 | 3 | 4 | 5 | ||
|---|---|---|---|---|---|---|
| A | 3 | 4 | 5 | 1 | 9 | ← 更新できる方 |
| B | 4 | 4 | 4 | 5 | 5 | ← 固定値 |
(1 2) (2 3) (4 5) 番目に対して操作できるとしたとき、
| 1 | 2 | 3 | 4 | 5 | ||
|---|---|---|---|---|---|---|
| A | 3 | 4 | 5 | 2 | 8 | |
| +1 | -1 | (1 2) 番目を操作 | ||||
| 4 | 3 | |||||
| +1 | -1 | (2 3) 番目を操作 | ||||
| 4 | 4 | (1 2 3) 番目が B と一致した | ||||
| +3 | -3 | (4 5) 番目を操作 ※ (+1 -1) を3回適用 | ||||
| 5 | 5 | (4 5) 番目も B と一致した | ||||
| A (最終値) | 4 | 4 | 4 | 5 | 5 | A と B は |
| B | 4 | 4 | 4 | 5 | 5 | 一致した |
のような流れで、更新した A と、固定値の B が一致するので答えは Yes になる。
2. 一致しない場合
仮に A と B が次のようになっていて、
| 1 | 2 | 3 | ||
|---|---|---|---|---|
| A | 3 | 4 | 5 | ← 更新できる方 |
| B | 4 | 4 | 3 | ← 固定値 |
(1 2) (2 3) 番目に対して操作できるとしたとき、
| 1 | 2 | 3 | ||
|---|---|---|---|---|
| A | 3 | 4 | 5 | |
| +1 | -1 | (1 2) 番目を操作 | ||
| 4 | 3 | |||
| +1 | -1 | (2 3) 番目を操作 | ||
| 4 | 4 | 3番目を3にしたいので | ||
| +1 | -1 | 再度 (2 3) 番目を操作するも | ||
| 5 | 3 | 今度は2番目が一致しなくなる | ||
| A (打ち切り) | 4 | 5 | 3 | A と B は |
| B | 4 | 4 | 3 | 絶対に一致しない？ |
のような流れになる。どの順番で A を更新しても、一方を加算すると一方を減算しないといけないので B と一致させるのは難しい。いや、難しいというよりも、そもそも、3 4 5 の合計と 4 4 3 の合計が同じじゃないとダメなのでは？──と、うすうす気づく。
考え方を整理する
(1 2) (2 3) 番目に対して操作が可能な場合、(1 2 3) 番目の値を自由に調整できる。たとえば (1 2 3) 番目の値が [3, 4, 5] であれば、
[3, 4, 5].sum # => 12
[4, 4, 4].sum # => 12
[6, 6, 0].sum # => 12
[2, 5, 5].sum # => 12
[0, 0, 12].sum # => 12
のようになる。これは RPG でプレイヤーのステイタス値を割り振る感じに似ている。どう割り振ってもステイタスの合計値は同じだということ。だから何番目を何の値にすべきかについてはそれほど重要ではない。重要なのは B の並びと一致させることが可能かどうかなので、それには両方の合計を比較するだけでよい。
コード
N, M = gets.split.collect(&:to_i) # => [3, 2]
A = gets.split.collect(&:to_i) # => [1, 2, 3]
B = gets.split.collect(&:to_i) # => [2, 2, 2]
CD = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2], [2, 3]]
ds = DisjointSet.new(1..N).unites(CD)
success = ds.groups.all? do |_, nodes|
a = nodes.collect { |e| A[e.pred] }.sum
b = nodes.collect { |e| B[e.pred] }.sum
a == b
end
success # => true
puts success ? "Yes" : "No"
Discussion