今日の精進(20191230)

なんだかあまりできなかった。。。

XOR Circle

完全解説AC。というか解説通りに実装したら通ったよというだけなのでもう少し考える。

問題文

すぬけ君は
N枚の帽子を持っています。i枚目の帽子には整数 aiが書かれています。
N頭のラクダが円環状に並んでいます。 すぬけ君はそれぞれのラクダに1枚の帽子を被せようとしています。どのラクダについても以下の条件が成立するような帽子の被せ方が存在するならば Yes を、そうでなければ No を出力してください。

  • 両隣のラクダが被っている帽子に書かれた数のビットごとの排他的論理和が自身の被っている帽子に書かれた数と等しい

制約

  • 入力はすべて整数
  • $3 <= N <= 10^5$
  • $0 <= a <= 10^9$

考察

(解説より)

両隣の排他的論理和と自分の番号が同じ <--> 連続する3つの排他的論理和が0

まずこの理屈がわからなかったので確認した。
ex. 3, 6, 5と並んでいる場合
3 xor 5 = 6
6 xor 6 = 0
なんとなく2進数でいろいろ試していたらそうなるのは分かった。というか当たり前な理屈だった…。
というわけで、条件を満たすには次が成り立つ必要がある。
$$x_i\ xor\ x_{i+1}\ xor\ x_{i+2} = 0 $$
また、一つ隣の連続した3つでも成り立つ必要があるので、
$$x_{i+1}\ xor\ x_{i+2}\ xor\ x_{i+3} = 0 $$
も満たされる。
このことから、$x_i = x_{i+3}$となるので、入力Aは3つの整数からなる配列である必要がある。
整数が4種類以上ある場合は即成立できないが、コーナケースとしてすべて0な場合と、2種類の整数かつ1つは0(N/3個)というのも考えられる。
以上の考察から実装を行う。

実装

# coding: utf-8  
N = int(input())  
A = list(map(int, input().split()))  
# A.sort()  
d = {}  
for i in range(N):  
    a = A[i]  
    if a not in d.keys():  
        d[a] = 1  
    else:  
        d[a] += 1  
flag = True  
if len(d.keys()) == 1:  
    if list(d.keys())[0] == 0:  
        flag = True  
    else:  
        flag = False  
elif len(d.keys()) == 2:  
    keys = list(sorted(list(d.keys())))  
    if d[keys[0]] == N // 3:  
        flag = True  
    else:  
        flag = False  
elif len(d.keys()) == 3:  
    keys = list(d.keys())  
    if keys[0] ^ keys[1] ^ keys[2] == 0:  
        if d[keys[0]] == d[keys[1]] == d[keys[2]]:  
            flag = True  
        else:  
            flag = False  
    else:  
        flag = False  
else:  
    flag = False  
print("Yes" if flag else "No")  

こんなの思いつかないよ(´;ω;`)XORにもっとなれる必要性を痛感した。

感想

今日は用事があったのでほとんど精進できなかったが、XORの問題に取り組めたのはよかった。