[ARC097/ABC097 D] Equals
森を作って節と連番が同じ木か調べる問題。
整数のペアは添字かそれとも値か？
問題文の (x1, y1) が何を指しているのかがわかりにくい。こちらの解説によると「添字ではない」と書かれている。つまり値だということ。ところが、問題入力例1の説明には、
[5, 3, 1, 4, 2]
から 1 と 3 を入れ替えると、
[1, 3, 5, 4, 2]
になると書いてある。それは 1 と 3 を添字として解釈した場合と等しい。もし、1 と 3 の値を入れ替えると、
[5, 1, 3, 4, 2]
になるので例1の説明とは異なる。したがって、整数のペアは「添字」なのではないかと思われる。
問題を例1を使って単純化する
-
5 3 1 4 2を入れ替えたとき1 2 3 4 5と並びが一致する部分を最大にしたい - 入れ替えることができる位置は (1, 3) または (5, 4) 番目と決まっている
例1のシミュレーション
初期状態
| p[] | 1..N | 同じ？ |
|---|---|---|
| 5 | 1 | |
| 3 | 2 | |
| 1 | 3 | |
| 4 | 4 | ○ |
| 2 | 5 |
同じ箇所が 1 つあるので、ここで入れ替えることができない場合の答えは 1 になる。
まず (1, 3) 番目の入れ替え
| p[] | 1..N | 同じ？ | |
|---|---|---|---|
| 1 | 1 | ○ | |
| 3 | 2 | ||
| 5 | 3 | ||
| 4 | 4 | ○ | |
| 2 | 5 |
もう一カ所一致するようになった。
次に (5, 4) 番目の入れ替え
| p[] | 1..N | 同じ？ | |
|---|---|---|---|
| 1 | 1 | ○ | |
| 3 | 2 | ||
| 5 | 3 | ||
| 2 | 4 | ||
| 4 | 5 |
これは、入れ替えない方がよかったとわかる。
つまり (1, 3) 番目を入れ替えた場合がもっとも多く2箇所に一致するので答えは2になる。
コード (WA)
以上を実装すると、
N, M = gets.split.collect(&:to_i) # => [5, 2]
P = gets.split.collect(&:to_i) # => [5, 3, 1, 4, 2]
XY = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 3], [5, 4]]
av = (1..N).collect.with_index { |e, i|
if P[i] == e # 入れ替える前から同じ？
true
else
XY.any? do |x, y|
a = P.dup
x -= 1
y -= 1
a[x], a[y] = a[y], a[x] # 入れ替えてみて
a[i] == e # 同じになるか？
end
end
}
av # => [true, false, false, true, false]
av.count(&:itself) # => 2
となる。ところが、このコードでは例2と例3が通らない。何がいけなかったのか？
問題文には「好きなだけ交換してよい」とある。この言い回しがこの問題のもっとも重要な部分で、好きなだけ交換してよいということは、特定の値があっちこっちに移動するということでもある。隣同士の入れ替えに限定してはいないものの、パネポンのようなセルの操作を想像するとわかりやすい。
ただし「どこに何をどの順番で交換していけばよいか？」「最悪、何回目で交換を打ち切ればいいか？」などと考え出すと完全に詰んでしまう。
ここでは単に移動可能な位置を連鎖するようにグループ化していくだけでよい。仮に (1, 3) と (3, 5) 番目が交換可能であれば、1 番目の値が 5 番目まで移動できるのは明白なので、どこに何を持っていくかは重要でなく、1-3-5 番目がグループであることだけが重要になってくる。
コード (AC)
値ではなく添字(=番目)をグループ化している。
N, M = gets.split.collect(&:to_i) # => [10, 8]
P = gets.split.collect(&:to_i) # => [5, 3, 6, 8, 7, 10, 9, 1, 2, 4]
XY = M.times.collect { gets.split.collect(&:to_i) } # => [[3, 1], [4, 1], [5, 9], [2, 5], [6, 5], [3, 5], [8, 9], [7, 9]]
ds = DisjointSet[XY]
P.each.with_index(1).count { |*e| ds.same?(*e) } # => 8
Discussion