はじめに
前回の記事([Python] 排他的論理和についてまとめてみる)を書くきっかけになったAtCoderの問題を解いてみました。
この問題、嘘回答があるらしく、その辺をまとめたいと思います。
実際の問題
以下に問題を載せます。
AGC 035 A - XOR Circle
###問題文
すぬけ君は$N$枚の帽子を持っています。$i$枚目の帽子には整数$a_i$が書かれています。
$N$頭のラクダが円環状に並んでいます。 すぬけ君はそれぞれのラクダに$1$枚の帽子を被せようとしています。
どのラクダについても以下の条件が成立するような帽子の被せ方が存在するならば $Yes$ を、そうでなければ $No$ を出力してください。
- 両隣のラクダが被っている帽子に書かれた数のビットごとの排他的論理和が自身の帽子に書かれいた数と等しい。
###制約
- 入力はすべて整数
- $3\leq N \leq10^2$
- $0\leq a_i \leq10^9$
入力
$N$
$a_1$ $a_2$ ... $a_n$
出力
答えを出力せよ。
嘘回答
まずは、排他的論理和の性質からまとめます。
x ^ y == y ^ x
(x ^ y) ^ z == x ^ (y ^ z)
x ^ x == 0
x ^ 0 == x
x ^ y == x ^ y
z ^ x ^ y == x ^ y ^ z
次に、問題を整理します。
円形なので、以下のような式になります。
\begin{align}
a_i \oplus a_2 &= a_1\\
a_1 \oplus a_3 &= a_2\\
a_2 \oplus a_4 &= a_3\\
\vdots\\
a_{i-2} \oplus a_i &= a_{i-1}\\
a_{i-1} \oplus a_1 &= a_i\\
\end{align}
これを上から下に向けて、代入していきます。
a_i \oplus a_2 \oplus a_3 \oplus a_3 \cdots a_{i-2} \oplus a_{i-1} \oplus a_1 = a_i
この式を整理すると、以下の式となります。
0 \oplus a_1 \oplus a_2 \oplus a_3 \oplus a_3 \cdots a_{i-2} \oplus a_{i-1} \oplus a_{i} = 0
すなわち、すべての値の排他的論理和が0になれば、良いことが分かります。
以上を考慮して書いたコードが次のようになります。
from sys import stdin
def main():
_ = int(input())
a_lists = [int(x) for x in stdin.readline().rstrip().split()]
z = 0
for a in a_lists:
z ^= a
if z == 0:
print("Yes")
else:
print("No")
if __name__ == "__main__":
main()
実際に提出するとACとなりました。
なぜ嘘回答なのか？
一見良さそうな解法ですが、この解法には落とし穴があります。
簡単な例として、$N=4,;a_1=a_2=a_3=a_4=1$の時を考えてみましょう。
上記の方法では
\begin{align}
0 \oplus 1 \oplus 1 \oplus 1 \oplus 1
&= 0 \oplus 0 \oplus 0\\
&= 0\\
\end{align}
となり、条件を満たします。
しかし、$1 \oplus 1 \neq 1$であり、問題文の条件を満たさないので、これだけだと不正解です。
本当の解法
嘘回答では条件が足りないので、必須条件を探しに行きます。
まずは以下の式について考えます。
便宜上、上の式を$A$、下の式を$B$とします。
a_1 \oplus a_3 = a_2 ...A\\
a_2 \oplus a_4 = a_3 ...B\\
整理するため$A$の式の両辺に $\oplus a_3$ 、$B$の式の両辺に $\oplus a_4$を行います。
a_1 = a_2 \oplus a_3\\
a_2 = a_3 \oplus a_4\\
$B$の$a_2$を$A$の$a_2$に代入します。そして式を整理していくと・・・
a_1 = a_3 \oplus a_4 \oplus a_3\\
a_1 = a_3 \oplus a_3 \oplus a_4 \\
a_1 = 0 \oplus a_4 \\
a_1 = a_4\\
となりました。同様に$a_2,a_3$を求めると、
a_2 = a_5 \\
a_3 = a_6 \\
となり、すなわち
$$a_i = a_{i+3}$$
となります。よって多くても3種類の値しかないことが分かります。
まとめると、以下の条件を満たせばよさそうですね。
a_1 \oplus a_2 \oplus a_3 = 0\\
かつ\\
a_i = a_{i+3}
この条件を満たすうえで、以下の場合分けを考えます。
- 3種類とも異なる値の時 $a_1\neq a_2\neq a_3$
- 2種類異なる値の時 $a_1 = a_2\neq a_3;or; a_1 \neq a_2 = a_3$
- すべて同じ値の時 $a_1 = a_2 = a_3$
3種類とも異なる値の時
この場合は以下の条件を満たす必要があります。
a_1 \oplus a_2 \oplus a_3 = 0\\
a_1\;,a_2\;,a_3\;がそれぞれN/3枚\\
→Nは3の倍数
2種類異なる値の時
例えば、$a_1 \oplus a_1 \oplus a_3 = 0$ を考えます。
2種類異なるということは、必ず同じ値を$\oplus$することになります。
また、同じ値を$\oplus$すると必ず$0$になるため、片方の値は$0$でなければなりません。
上の式で考えると$a_3 = 0$である必要があります。
つまり、条件は以下のようになります。
a_iが2N/3枚のとき\\
もう一つの値が0でN/3枚のとき
すべて同じ値の時
$a_1 \oplus a_2 \oplus a_3 = 0 and a_1 = a_2 = a_3$ を満たす条件はすべて$0$の時しかありません。よって以下の条件になります。
a_i = 0
またこの場合は$N$がどんな値でも大丈夫です。
以上を考慮してコードを書くと以下のようになりました。
from sys import stdin
def main():
N = int(input())
a_list = [int(x) for x in stdin.readline().rstrip().split()]
a_set = set(a_list)
if len(a_set) == 1:
if sum(a_set) == 0:
print("Yes")
else:
print("No")
elif len(a_set) == 2:
a_1, _2 = sorted(a_set)
if a_1 == 0:
if a_list.count(a_1) * 3 == N:
print("Yes")
else:
print("No")
else:
print("No")
elif len(a_set) == 3:
a_1, a_2, a_3 = a_set
if a_list.count(a_1) == a_list.count(a_2) and a_list.count(a_2) == a_list.count(a_3):
if a_1 ^ a_2 == a_3:
print("Yes")
else:
print("No")
else:
print("No")
else:
print("No")
if __name__ == "__main__":
main()
提出すると無事ACとなりました。
感想
$A$問題でここまで考える必要があるのは大変ですね・・・
排他的論理和の問題は時々出てくるので、問題パターンを覚えていきたいです。