排他的記事。

￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣

まず始めに、宣伝させてください、申し訳ない。

ちょっと悲しき放置プレイになっているので宜しくお願い致します。

￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣

では、改めて、今日の話に参りましょう。

排他的論理和をご存知だろうか。僕はあまりご存知無かった。

排他的論理和　－　論理演算の一種、XOR演算

論理演算　－　0、1の二通りの状態を取る真偽値の間で行われる演算

XOR演算：

　　　　a　　　b　　　a ^ b（a XOR b）の演算結果

　　　　1　　　1　　　　　　　　　　0
　　　　1　　　0　　　　　　　　　　1
　　　　0　　　1　　　　　　　　　　1
　　　　0　　　0　　　　　　　　　　0

例：

４＾6

　　　　　　　　100（4の二進表記）
　　　　　＾）　110（6の二進表記）
　　　　　￣￣￣￣￣￣￣￣￣￣￣￣￣   
　　　　　　　　010

　　　　　　∴　2（010の十進表記）
 

問題：

A、B、C、Dの４人がいて、それぞれ本人も知らない秘密の番号を持っている。

自分以外の３人の秘密の番号の排他的論理和が、

A：20　B：11　C：9　D：24

であるとき、４人それぞれの秘密の番号を求めよ。　

つまり、

〇〇〇（Bの秘密の番号）＾△△△（Cの秘密の番号）＾□□□（Dの秘密の番号）
　　　　　　　　　　　　　　　　　　　　　　　　　　＝10100（20の二進表記）

という情報から、それぞれの番号を求めよ、ということになる。

まあ例えば、

　　　　　　　　　B　11000　（24）
　　　　　　　　　C　10001　（17）
　　　　　　＾）　D　11101　（29）
　　　　　　￣￣￣￣￣￣￣￣￣￣￣￣￣  
　　　　　　　　　　   10100　（20）

などが候補として考えられる。

条件が１つだけなら答えは無限にあるが、条件は４つあるので答えは１つになる。

さて、４人全員の秘密の番号を求めよう。

解き方に行く前に排他的論理和のことは一旦忘れて、普通の四則演算をしよう。

問題：

A、B、C、Dの４人がいて、それぞれ本人も知らない秘密の番号を持っている。

自分以外の３人の秘密の番号の和が、

A：34　B：55　C：53　D：38

であるとき、４人それぞれの秘密の番号を求めよ。　

これは中学校でやる連立方程式の問題だ。

与えられた条件を式にすると、

　　　B ＋ C + D ＝ 34　　　・・・①
　　　A ＋ C + D ＝ 55　　　・・・②
　　　A ＋ B + D ＝ 53　　　・・・③
　　　A ＋ B + C ＝ 38　　　・・・④

どう解いても良いが、簡単なのは、

　　　　B ＋ C + D ＝ 34
　　　　A ＋ C + D ＝ 55
　　　　A ＋ B + D ＝ 53
　＋）　A ＋ B + C ＝ 38
　￣￣￣￣￣￣￣￣￣￣￣￣￣
　　   3( A ＋ B + C + D ) = 180

　∴　A ＋ B + C + D = 60　　　・・・⑤

⑤－①より　　A ＝ 26
⑤－②より　　B ＝ 5
⑤－③より　　C ＝７
⑤－④より　　D ＝ 22

という解き方だ。

これがね、排他的論理和でも使えるんよ。

問題を戻して。

問題：

A、B、C、Dの４人がいて、それぞれ本人も知らない秘密の番号を持っている。

自分以外の３人の秘密の番号の排他的論理和が、

A：20　B：11　C：9　D：24

であるとき、４人それぞれの秘密の番号を求めよ。　

与えられた条件を式にすると、

　　　B ＾ C ＾ D ＝ 20　　　・・・①
　　　A ＾ C ＾ D ＝ 11　　　・・・②
　　　A ＾ B ＾ D ＝ 9　　　  ・・・③
　　　A ＾ B ＾ C ＝ 24　　　・・・④

これがね、

　　　　B ＾ C ＾ D ＝ 20
　　　　A ＾ C ＾ D ＝ 11
　　　　A ＾ B ＾ D ＝ 9
　＾）　A ＾ B ＾ C ＝ 24
￣￣￣￣￣￣￣￣￣￣￣￣￣   
　　　　A ＾ B ＾ C ＾ D ＝ 14　　　・・・⑤

⑤ ＾ ①より　　A ＝ 26
⑤ ＾ ②より　　B ＝ 5
⑤ ＾ ③より　　C ＝７
⑤ ＾ ④より　　D ＝ 22

で簡単に答えが出るんよ！

⑤の式が何で出るの？

　　　(B ＾ C ＾ D) ^ (A ＾ C ＾ D) ^ (A ＾ B ＾ D) ^ (A ＾ B ＾ C)

これを計算してる訳なんだけど。

ここで、
 

排他的論理和の性質

　　　　a ^ b == b ^ a　　　　　　　　・・・（１）

　　　　(a ^ b) ^ c == a ^ (b ^ c)　　　・・・（２）

　　　　a ^ x ^ x == a　　　　　　　　・・・（３）

　 　　(B ＾ C ＾ D) ^ (A ＾ C ＾ D) ^ (A ＾ B ＾ D) ^ (A ＾ B ＾ C)

性質（２）より

　　＝ B ＾ C ＾ D ＾ A ＾ C ＾ D ＾ A ＾ B ＾ D ＾ A ＾ B ＾ C

性質（１）より

　　＝ A ＾ A ＾ A ＾ B ＾  B ＾ B ＾ C ＾ C ＾ C ＾ D ＾ D ＾ D

性質（３）より

　　＝ A ＾ B ＾ C ＾ D

で、A ＾ B ＾ C ＾ D がわかれば、
 

                    (A ＾ B ＾ C ＾ D) ＾ (B ＾ C ＾ D) 
                 = A ＾ B ＾  B ＾ C ＾  C ＾ D ＾ D
                 = A

となって答えが出せる。

これって常識なの？

Atcoder では １万人 中 ４千人 も知ってたみたいなんだけど。

僕は知らなかったせいで知ってれば超簡単な問題を落としたよ。

元の問題：

コード：

N = int(input())
A = list(map(int, input().split()))

xor = 0
for i in A:
   xor ^= i

for j in range(N):
   print(xor^A[j], end=' ')

見ろ、E 問題がゴミのようだ。

ホントは最後のところ、

if i != 0:
       print(' ', end='')
   print(A^a[i], end='')
print()

みたいにしなきゃダメなはずだけど、Atcoder は最後に変なスペース入ってても改行してなくても正解になるんよね。Paiza だと不正解になったはず。

さて、ここまで読んだ方はいるのだろうか。

むしろ、ここだけ読んでる方はいるかもしれない。

これ昨日の E 問題が解けなかった人にはスーパー為になる記事のはずなんだけど。

もの凄いニッチな話題でも同類の人に見て貰えるのがブログの良いところでしょ。

何かね、ALIS に Atcoder の話を書いてると小学校のときクラスで誰もやってない大航海時代IIの話をしてる時の感じになるんよね。何そのゲーム、知らね、みたいな。

そういうの言ってても、あ、俺それ知ってる、面白いよねって言って貰えるのがブログの良いところでしょ、違うん、違うんか？あ゛ぁ？？やさぐれるぞ！

こういうの書いてるのも、何か読むとこねぇわ、って思われたくなくて、ちょっとでも雑談を書こうって気持ちなんだからね、皆がわかる話をする為に大航海時代IIをする時間を削ってバラエティー番組とか見てる感じ。もう！ALISよ、頑張ってくれ！

まあ良いや、後で はてなブログ にコピペしよう。