[ABC126 E] 1 or 2
木の数を求める問題。
A[X] と A[Y] の組み合わせ
各カードには整数 1 または 2 が書かれています。
とのことから A[X] と A[Y] の組み合わせは、
[1, 2].product([1, 2]) # => [[1, 1], [1, 2], [2, 1], [2, 2]]
の4パターンであることがわかる。
A[X] + A[Y] + Z = 偶数 から分かること
A[X] + A[Y] + Z = 偶数 の式に、その4パターンと、奇数の Z (1 でも 3 でも 5 でも結果は変わらなので仮に 1 とする) を代入すると、
(1 + 1 + 1).odd? # => true
(2 + 2 + 1).odd? # => true
(1 + 2 + 1).odd? # => false
(2 + 1 + 1).odd? # => false
成立するのは [1, 1] と [2, 2] の場合のみとわかる。
同様に偶数の Z (2 でも 4 でも 6 でも結果は変わらないので仮に 2 とする) で試してみると、
(1 + 1 + 2).odd? # => false
(2 + 2 + 2).odd? # => false
(1 + 2 + 2).odd? # => true
(2 + 1 + 2).odd? # => true
成立するのは [1, 2] と [2, 1] の場合のみとわかる。
したがって A[X] と A[Y] の組み合わせは次のようになる。
- Z が偶数 → [1, 1] or [2, 2]
- Z が奇数 → [1, 2] or [2, 1]
例2のシミュレーション
| X | Y | Z |
|---|---|---|
| 1 | 2 | 1 |
| 2 | 3 | 2 |
| 1 | 3 | 3 |
| 4 | 5 | 4 |
| 5 | 6 | 5 |
1ターン目
X Y Z = 1, 2, 1 を A[X] + A[Y] + Z に代入する。
A[1] + A[2] + 1
ここで Z の値に注目すると 1 が奇数なので、さっき出てきた、
- Z が奇数 → [1, 2] or [2, 1]
に当てはまる。ということは、仮にここで A[1] をめくったとき、
- 1 なら A[2] は 2
- 2 なら A[2] は 1
だとわかる。同様に A[2] をめくったとき、
- 1 なら A[1] は 2
- 2 なら A[1] は 1
だとわかる。つまり、一方をめくれば一方がわかる。
この「めくり行為」を問題では「1コスト必要な魔法」と表現していて「最小何コストですべてのカードの中身を知ることができるか？」という問いなので、もし、(N = 2 でかつ) この入力例が1ターン目で終わっていれば「1めくり」で答えは 1 になる。
今回はめくらなかったことにして、コメントだけ入れて2ターン目に進む。
A[1] + A[2] + 1 # A[1], A[2] は [1, 2] or [2, 1]
2ターン目
X Y Z = 2, 3, 2 なので、
A[1] + A[2] + 1 # A[1], A[2] は [1, 2] or [2, 1]
A[2] + A[3] + 2
と追記して1ターン目と同様に Z に注目すると今度は偶数なので、
- Z が偶数 → [1, 1] or [2, 2]
に当てはまり、A[2], A[3] は [1, 1] か [2, 2] だとわかったのでコメントしておく。
A[1] + A[2] + 1 # A[1], A[2] は [1, 2] or [2, 1]
A[2] + A[3] + 2 # A[2], A[3] は [1, 1] or [2, 2]
ここでまた仮に A[1] をめくってみるとどうなるか？ 1ターン目で A[1] がわかれば A[2] も確定するのはわかった。その A[2] は2ターン目の式にも出てくるので、つまり A[1] がわかれば A[3] まで連鎖して確定する。たとえば、
A[1] が 1 の場合:
1 + 2 + 1
2 + 2 + 2
A[1] が 2 の場合:
2 + 1 + 1
1 + 1 + 2
したがって、(N = 3 でかつ) ここで入力が終わったとしても「1めくり」で答えは 1 である。
3ターン目
X Y Z = 1, 3, 3 なので、Z が奇数のときのパターンでコメントしておく。
A[1] + A[2] + 1 # A[1], A[2] は [1, 2] or [2, 1]
A[2] + A[3] + 2 # A[2], A[3] は [1, 1] or [2, 2]
A[1] + A[3] + 3 # A[1], A[3] は [1, 2] or [2, 1]
また、(N = 3 でかつ) ここで入力が終わったとした場合に、A[1], A[2], A[3] のどれをめくったとしても連鎖ですべてのカードが確定するので、答えは 1 になる。
4ターン目
X Y Z = 4, 5, 4 なので、Z が偶数のときのパターンでコメントしておく。
A[1] + A[2] + 1 # A[1], A[2] は [1, 2] or [2, 1]
A[2] + A[3] + 2 # A[2], A[3] は [1, 1] or [2, 2]
A[1] + A[3] + 3 # A[1], A[3] は [1, 2] or [2, 1]
A[4] + A[5] + 4 # A[4], A[5] は [1, 1] or [2, 2]
ここで仮に A[1] をめくると A[3] までは確定するが A[4] と A[5] には連鎖が届かないのがわかる。A[4] と A[5] を知るには、もう1めくり必要になる。したがって (N = 5 でかつ) ここで入力が終わったとした場合の答えは 2 になる。
5ターン目
X Y Z は 5, 6, 5 なので、Z が奇数のときのパターンでコメントしておく。
A[1] + A[2] + 1 # A[1], A[2] は [1, 2] or [2, 1]
A[2] + A[3] + 2 # A[2], A[3] は [1, 1] or [2, 2]
A[1] + A[3] + 3 # A[1], A[3] は [1, 2] or [2, 1]
A[4] + A[5] + 4 # A[4], A[5] は [1, 1] or [2, 2]
A[5] + A[6] + 5 # A[5], A[6] は [1, 2] or [2, 1]
ここで入力は終わりになる。これまでの法則からすると A[X] と A[Y] のどちらかが繋がっていると連鎖して確定するのがわかった。繋がっているグループは 1-2-3 と 4-5-6 の二つである。したがって、それぞれのグループに対してどれかを1枚めくれば全カードが確定するので最終的な回答は「2グループ」こと「2めくり」の 2 になる。
グループにまとめる
それには素集合データ構造が適しているので入力のペア
[1, 2]
[2, 3]
[1, 3]
[4, 5]
[5, 6]
だけを見て森を作る。そして木の数が答えになる。
Z の値はいらない？
カードの番号を知るには必要だが、連鎖するグループにまとめる段階ではいらない。(ここで疑問に感じる場合、例2のシミュレーションを再度確認する)
コード
N, M = gets.split.collect(&:to_i) # => [6, 5]
XYZ = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2, 1], [2, 3, 2], [1, 3, 3], [4, 5, 4], [5, 6, 5]]
xy = XYZ.collect { |x, y, _| [x, y] } # => [[1, 2], [2, 3], [1, 3], [4, 5], [5, 6]]
p DisjointSet.new(1..N).unites(xy).tree_count # => 2
Discussion