ABC126_E – 1 or 2

問題
提出
1. 感想
  1. 1回目

問題

E - 1 or 2

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

提出

Submission #45115605 - AtCoder Beginner Contest 126

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

感想

1回目

解けた。
$A_{X_i}+A_{Y_i}+Z_i$が偶数という条件だが、これは$X_i,Y_i$のどちらかがわかればもう一方もわかると言い換えできる。
$Z_i$が偶数の時、$A_{X_i}+A_{Y_i}$は偶数になる。$A_{X_i}+A_{Y_i}$が偶数になるには、$(A_{X_i},A_{Y_i}) = (1,1) or (2,2)$のみ。
$Z_i$が奇数の時、$A_{X_i}+A_{Y_i}$は奇数になる。$A_{X_i}+A_{Y_i}$が奇数になるには、$(A_{X_i},A_{Y_i}) = (1,2) or (2,1)$のみ。
つまり、片方が分かればもう片方も分かる。

片方が分かればもう片方も分かる関係になっているグループを作ることにする。
この時、このグループの中で1つでも分かれば他は全て分かることになる。
このグループはUnionFindを使えば簡単に作れる。
UnionFindのグループ数が答えになる。

ちなみに、UnionFindはatcoder-libraryにDSUという名前である。

Page not found · GitHub Pages