AIで解説 AtCoder攻略　XOR・ビット演算

XOR・ビット演算ページの位置づけ

この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。

XORの線形性とビットごとの独立性を利用する計数・構成をまとめるページです。

問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。

まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。

最初の一問として、ABC246 A Four Points（公式解説）を解きます。長方形の各座標は2回ずつ現れ、欠けた頂点の座標だけ1回になります。XORは同じ値を2回計算すると消えるので、3点をXORすれば答えが残ります。

x_answer = 0
y_answer = 0
for _ in range(3):
    x, y = map(int, input().split())
    x_answer ^= x
    y_answer ^= y

print(x_answer, y_answer)

座標を数え上げる方法でもO(1)ですが、XORなら追加の辞書を使わずO(1)メモリで書けます。

このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。

問題	公式解説	出題意図	difficulty
ABC246 A Four Points	公式解説	長方形の3頂点のx,y座標をそれぞれXORして、欠けた頂点を復元する。	-670
ABC270 A 1-2-4 Test	公式解説	1,2,4の試験結果をビットORして不足結果を判定する。	-473
ABC405 B Not All	公式解説	公式Editorialの方針を not all bitmask として整理する。	-430
ABC396 D G. Minimum XOR Path	公式解説	Enumerate all simple paths from vertex 1 to N with DFS and minimize their edge-label XOR.	601
ABC418 D G. XNOR Operation	公式解説	公式Editorialの方針を xnor bitwise dp として整理する。	821

問題	公式解説	出題意図	difficulty
ABC301 D G. Bitmask	公式解説	Set wildcard bits greedily while keeping the binary value at most N.	885
ABC356 D G. Masked Popcount	公式解説	Official editorial intent is classified as masked popcount formula.	886
ABC238 D G. AND and SUM	公式解説	x+y=Sとx&y=Aの関係S−2Aを利用し、ビット条件を満たす非負x,yの存在を判定する。	921
ABC407 D G. Domino Covering XOR	公式解説	公式Editorialの方針を domino xor dp として整理する。	930
ABC470 C Inc, Dec, Xor	公式解説	Use bitwise-state DP for increment, decrement, and XOR operations.	1006

問題	公式解説	出題意図	difficulty
ABC347 D G. Popcount and XOR	公式解説	Official editorial intent is classified as popcount xor construction.	1041
ABC365 E H. Xor Sigma Problem	公式解説	Official editorial intent is classified as xor pair sum bit.	1102
ABC337 E H. Bad Juice	公式解説	Official editorial intent is classified as interactive bitmask query.	1155
ABC236 D G. Dance	公式解説	未使用者から最小番号を選び、相手を全列挙する再帰でペアXORの最大値を探索する。	1190
ABC147 D Xor Sum 4	公式解説	XORは各ビット独立であることを使い、各ビットの0個数と1個数の積を足し上げる。	1205