🌳
[ABC206 D] KAIBUNsyo
全体の辺の数を求める問題。
一言で解法
この問題は考え方がめちゃくそ難しくて公式解説もほとんど理解できなかったので答えから言うと最初に書いちゃってるけど、
- 全体の辺の数
そのものになる。
具体的には、もし順列が (A X Y B) なら (A B) (X Y) で素集合森を作り、その結果の A-B X-Y のハイフンの数 2 が答えになる。
例1〜2 の素集合森を作って確認する
例 1
(1 5 3 2 5 2 3 1) から (1 1) (5 3) (3 2) (2 5) で森を作る → 答え 2 回
例 2
(1 2 3 4 1 2 3) から (1 3) (2 2) (3 1) (4 4) で森を作る → 答え 1 回
たしかに、どちらも辺の数と答えが一致している。
いろんなパターンで確認する
| 順列 | 素集合森 | 辺 | 順列だけを見てなんとなく考えたこと |
|---|---|---|---|
| A | A | 0 | すでに怪文書になっているので 0 回 |
| A A | A | 0 | すでに怪文書になっているので 0 回 |
| A B | A-B | 1 | A-B を A-A か B-B にするので 1 回 |
| A B A | A B | 0 | すでに怪文書になっているので 0 回 |
| A B C | A-C B | 1 | A-C を A-A とかに変更するだけなので 1 回 |
| A B C D | A-D B-C | 2 | 普通に考えて外側と内側で 2 回 |
| A A B B | A-B | 1 | 外側の A-B の更新で内側の A-B も同時に変わるので 1 回でいいはず |
| A B C C | A-C-B | 2 | 外側を A-A にすると内側が B-A になるので 2 回必要はなず |
| A B B B | A-B B | 1 | 外側の A-B だけでいいので 1 回 |
不思議なことに、なんとなく考えて出した回数と素集合森の辺の数が一致している。
初見考察
初見で問題を解こうとしたときに閃いてほしい考え方。
| 順列 | 更新するペア | 考察 |
|---|---|---|
| A B C D | A-D B-C | A-D B-C の2回更新が必要なのは確実 |
| A A B B | A-B A-B | 外側の A-B の更新で内側の A-B の更新が不要になる |
まず、前後をペアにしていく考えが出てこなかったら詰むのだけど、そこはクリアしたことにする。そして、前者のようにペアがユニークであればペアの個数だけ更新が必要になり、後者のように同じものがあれば二つ目の更新が不要になる。つまり、A-D B-C はそのまま残って A-B A-B は一つにしたい。この特徴に合ったデータ構造は、と来たら連想配列が出てきそうだが、素集合森も出てきてほしい。
問題文に含まれたヒント
以下の操作を0回以上何度でも
ときたら素集合データ構造であることが多い。
コード (AC)
N = gets.to_i # => 8
A = gets.split.collect(&:to_i) # => [1, 5, 3, 2, 5, 2, 3, 1]
xy = A.take(A.size.ceildiv(2)).zip(A.drop(A.size / 2).reverse) # => [[1, 1], [5, 3], [3, 2], [2, 5]]
p DisjointSet[xy].edge_count # => 2
Discussion