🙄

ABC197 C ORXORのbit全探索での解法メモ

2024/07/05に公開

C++

tech

記事を書く目的

特にコーナーケースの部分を理解するのに１週間近く掛かってしまったので、理解度の再チェックを
行う。

問題リンク

提出コード

31行目(提出コードの行数)

  int ans = 1 << 30;

補足として、intの限界値は2^30まで

32行目

  rep(bit,(1 << (n-1)))

aの区間を分けるかどうかをループで回す
nが3の場合、区間は最大2個で区間を分けるかどうかは2^2 = 4通り
00~11までをループで回す。

37,42行目

if (bit & (1 << i)) // 37

all ^= now; // 42

bit全探索のテンプレートなので、概要の説明は飛ばすが42行目がないと、最後に分けた区間は考慮されていないことに注意。
1 |3| 7 <= 左のケースの場合、最後の7でxorの計算が出来ていない。
つまりbitが3でiが2の場合、011 & 100 = 0でfalseとなる
そのため、ループが終わったタイミングで現在の結果all(2)とnow(7)のxorを取る
010 xor 111 = 101 = 5

補足

3,5,7等の2進数の移行方法として、2^n(1<<n)から逆算していくと、変換サイトでググったり2で割っていく計算しなくても出来る。

3は4が100だからその前の11が答え
5は4が100だからその次の101が答え
7は8が1000だからその前の111が答え

ただ数値が大きくなっていくとこのやり方だと無理が出てくるので入力例1などの簡単なケースな場合の使用に留めること