https://yukicoder.me/problems/no/534
続きを読む競技プログラミングにおける凸包問題まとめ
凸包
- 頂点集合の部分集合で構成されてる多角形が凸多角形かつ全ての頂点を包含する多角形
- O(NlogN)のアルゴリズムがある
- ここに色々紹介されている
- 動的凸包という概念もある
- 直線を使っても凸包が作れるらしい これ これもそれっぽいことをする
XOR Replace [AtCoder Grand Contest 016 D]
http://agc016.contest.atcoder.jp/tasks/agc016_d
解法
http://agc016.contest.atcoder.jp/submissions/1365639
www.youtube.com
解説放送の副読本として書きます。
一回の操作は配列とそのxor和とのswapに相当する。
これは解説放送の通り。
そのため、それぞれxor和を取って、multisetとして同じとなるかを判定して、同じでないなら-1で終了する。
(chk関数)
もし、2つのxor和が同じでない場合は最初にswapしておく。
これで解説放送45:30頃から出てくる図形と同じような状況になる。
これで各配列で異なっている要素を連結させていくのだが、普通にunionfindすると[0,10^9]となってしまうので、座圧して管理する。
2つの配列の同じ添字で合ってない個数をe, 連結成分の個数をcとする。
すると、答えはe + cとなるのだが、場合によっては1回分得をする場合がある。
rngさんも解説放送中に言っているが、「サイクルにxor和が含まれる場合」である。
これを判定しておき、もし含まれるならば、1回分減らす。
これで50:00頃から出てくる数式が答えとなる、e+c or e+c-1