No.74 貯金箱の退屈

Quiz

https://yukicoder.me/problems/no/74

Submit

https://yukicoder.me/submissions/339953

解法

  • 1枚だけでflipできるコインを調べておく
  • 2枚flipのとき
    • a, bを一緒にflipできるなら、Union Findでunite(a, b)しておく
    • 「一緒にflipできるグループ」ごとにまとまることになる
  • それを全てのコインについて回した後は、いくつかの木がある
  • 木ごとに、全部表にできるかチェックする
    • 木の中で、裏の枚数が偶数ならOK (2枚ごとflipできるため)
    • 裏の枚数が奇数であっても、木の中に「1枚だけでflipできるコイン」があるならOK

感想

  • Union Findの応用という感じで楽しかった