7K12 blog

猫でも分かるアルゴリズム解説

ABC126 E - 1 or 2

f:id:tkr987:20200502182625p:plain

https://atcoder.jp/contests/abc126/submissions/12464663

  • 集合の個数はunion-findとset.insert(uf.find(Ai))で実現できる。
  • 計算量は  O(N \log N)

f:id:tkr987:20200502184623p:plain

カードの数字が偶数と奇数に分かれるので、全部で4パターン列挙してみる。すると、Ax+Ay+ZのZが偶数でも奇数でも片方のカードが分かると相方のカードも分かる、と気づける。以下、芋づる式にカードが判明していく。芋づる式に判明したカードを1つの集合にすると集合の個数が答えになる。

 

dif12Kの中では数学的要素が少なく凡人でも解きやすい。