A - XOR Circle
[Q] https://atcoder.jp/contests/agc035/tasks/agc035_a
書きだしてみると、Yesパターンがとても少ないことに気づく。
1. 数字が1種類の場合、全部0ならYes
2. 2種類の場合、0の個数がN/3個ならYes
3. 3種類の場合、それぞれの個数がN/3個かつ、a^b^c==0ならYes
1. bitでとりあえず2つ書き出す。
001
010
おのずと
011
001
010
011
これは、
001
010
011 のループしかありえない。
2. 0を含む場合
000
001
おのずと
001
000
001
001
000
001
001 のループしかありえない。
3. 0だけ
000
000
000
000
...
000 のループしかありえない。Q. 全部の排他的論理和 == 0になればYes？
A. 嘘ケースが存在する。
6
4 7 3 3 6 5
これは No になるべきだが、YesになるコードでもACする。
4: 100
7: 111
3: 011
このあと、473473473でループさせる以外の選択肢がないから。
4^7^3^3^6^5 == 0 になるが、それだけだと不十分なのが分かる。実装。
int main(){
cincout();
ll N;
cin >> N;
map<ll, ll> M;
rep(i, N){
ll a;
cin >> a;
++M[a];
}
bool ok=false;
// 1種類: 全部0
if (M.size() == 1 && M.count(0)) ok = true;
// 2種類: 0がN/3
if (M.size() == 2){
if (M.count(0) && M[0] == N/3) ok = true;
}
// 3種類
if (M.size() == 3){
auto it = M.begin();
ll sum = 0;
rep(i, 3){
sum ^= it->first;
if (it->second != N/3) break;
if (i==2 && sum==0) ok = true;
++it;
}
}
if (ok) cout << "Yes" << endl;
else cout << "No" << endl;
}