XORを使う判断は、同じ値が対応関係の中で偶数回現れて消えるか、各bitを独立に数えられるかで決まります。 ABC246 Aでは、軸平行な長方形の3頂点から、x座標とy座標をそれぞれXORして欠けた頂点を復元できます。次のABC147 Dでは目的が変わり、全ての組のXORを列挙せず、各bitの0個数と1個数の積を足します。
XORで同じ値が消える理由
XOR（排他的論理和）は、同じ位置のbitが異なるときだけ1になる演算です。1bitだけを取り出すと、次の真理値表になります。
| 左のbit | 右のbit | 左 XOR 右 |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
この表から、同じ値をXORした x ^ x は全てのbitが0になり、0とのXORは元の値を保つため x ^ 0 = x です。XORはbitごとに計算でき、順番を変えても結果が変わらないので、式の中から同じ値の組を先にまとめて消せます。たとえば a ^ a ^ b ^ b は、(a ^ a) ^ (b ^ b) = 0 です。
したがって、XORの累積だけで値を復元できるのは、消したい値が対応関係の中で本当に2回ずつ現れる場合です。出現回数の条件がない問題へ、3個や全ての値を一度XORする方法をそのまま移してはいけません。全ての組の寄与を求める場合は、ABC147 Dのように目的に合わせてbit別の計数へ切り替えます。
ABC246 Aで3頂点から欠けた頂点を復元する
ABC246 Aの公式問題文は、各辺がx軸またはy軸に平行で、面積が0ではない長方形を題材にしています。4頂点のうち異なる3点の座標が与えられるので、残る1点の座標を求めます。入力は3行の整数 x_i y_i、出力は欠けた頂点のxとyを空白で区切った1行です。
| 項目 | 公式仕様 |
|---|---|
| 与えられるもの | 長方形の異なる3頂点。各行に整数のx座標とy座標。 |
| 長方形の条件 | 各辺がx軸またはy軸に平行、面積が0ではない。該当する長方形は一意。 |
| 座標の制約 | -100 ≤ x_i, y_i ≤ 100 |
| 求めるもの | 残る頂点のx座標とy座標。 |
軸平行な長方形では、x座標だけを見ると4頂点に同じ値が2回ずつ現れます。x座標を a, a, b, b と書けば、4点分のXORは a ^ a ^ b ^ b = 0 です。既知の3点分を x_1 ^ x_2 ^ x_3 として取り出すと、全体が0になるため、欠けたx座標だけが残ります。y座標も同じ関係になるので、xとyを別々に累積すればよいことになります。
ABC246 Aの公式解説は、3つのx座標のうちどの2つが等しいかを条件分岐で調べる方法を示しています。XORを使う方法は、その解説で確認されている「同じ座標が2つ、異なる座標が1つ」という条件を、自己打ち消しとして書いた参考実装です。公式解説の条件分岐と、ここで示すPythonコードを同じ解法として混同しないでください。
構成例でx座標とy座標のbitを追う
次は公式サンプルとは別の、規則を確かめるための構成例です。既知の3点を (1, 1)、(1, 4)、(6, 4) とすると、欠けた点は (6, 1) です。3bitで表し、xとyを別々に追います。
| 対象 | 3点のbit表現 | 先の2値をXOR | 残りをXORした結果 |
|---|---|---|---|
| x座標 | 001, 001, 110 |
001 ^ 001 = 000 |
000 ^ 110 = 110（6） |
| y座標 | 001, 100, 100 |
001 ^ 100 = 101 |
101 ^ 100 = 001（1） |
xでは1が2回現れて 001 ^ 001 が0になり、yでは4が2回現れて 100 ^ 100 が0になります。1回だけ現れた値がそのまま残るため、計算結果は (6, 1) です。この「同じ値の組を消し、1回の値を残す」操作が、3行の入力を読むコードの各累積変数に対応します。
ABC246 Aの完全Python参考コード
入力形式に合わせて3行を順に読み、x座標用とy座標用の2つの変数へXORを累積します。公式の問題文と解説をPythonへ書き下した参考コードです。
def main():
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)
if __name__ == "__main__":
main()x_answer ^= x は、現在の累積値と読んだx座標をXORして、累積値を更新する記法です。y_answer ^= y も同じようにy座標を更新します。
このコードが正しい理由
公式仕様の4頂点では、x座標の2つの値がそれぞれ2回ずつ現れます。既知の3点では、そのうち一方が2回、もう一方が1回現れるため、3つのx座標をXORすると、2回現れる値は0になり、欠けた頂点のx座標だけが残ります。x_answer はこの3値を順にXORしているので、欠けたx座標になります。
y座標も同じ理由で、y_answer は欠けたy座標になります。長方形が軸平行で面積0ではないという公式条件によってこの対応関係が成り立つため、xとyを別々に処理した2つの値を出力すれば答えです。
計算量と負の座標
入力は3点に固定され、各座標を定数回XORするため時間計算量は O(1) です。保持するのは2個の累積値なので、追加の空間計算量も O(1) です。制約は -100 ≤ x_i, y_i ≤ 100 で負の座標を含みますが、Pythonの整数XORは同じ整数どうしの x ^ x = 0 を満たします。コードは座標を別の型へ変換せず、そのまま処理します。不正な点の検証を加えないのは、公式入力で軸平行・非退化の長方形が一意に存在すると保証されているためです。
公式サンプルで入出力を確かめる
以下は公式問題文のサンプルです。入力を並べ替えたり変換したりせず、上のコードへそのまま与えます。
入力例1（公式）
-1 -1
-1 2
3 2期待出力
3 -1入力例2（公式）
-60 -40
-60 -80
-20 -80期待出力
-20 -40サンプル1ではx座標の -1, -1, 3 から3が残り、y座標の -1, 2, 2 から-1が残ります。負数を含む公式例でも、累積XORの考え方は変わりません。
ABC147 Dでは全ペアをbit別に数える
ABC246 Aは3点から1点を復元する問題でした。次の練習として、ABC147 Dでは、N個の整数から選ぶ全ての i < j の組について A_i XOR A_j を足し、その結果を 109 + 7 で割った余りを求めます。公式制約は 2 ≤ N ≤ 3 × 105、0 ≤ A_i < 260 です。
ここでは、ABC246 Aの3値XORを全ての組へそのまま適用しません。組を列挙すると組数は N(N - 1) / 2 になります。代わりにbit位置 k を1つ固定します。A_i XOR A_j のk bitが1になるのは、2つの値のk bitが異なるときだけです。k bitが1の値を ones 個、0の値を zeros 個とすると、異なる組は一方から1個ずつ選ぶ ones × zeros 個です。そのbitの重み 2k を掛けた ones × zeros × 2k が、全ペアへのk bitの寄与になります。
この数え方なら、各bitについて値の列を1回走査すればよく、公式解説PDFの説明どおりbitごとの独立性を利用できます。A_i < 260 なので、bit 0から59までを調べます。
ABC147 Dの公式サンプル1をbit別に追う
公式サンプル1の値 1, 2, 3 を3bitで 001, 010, 011 と書きます。bitごとに0と1の個数を数えると、全ペアの合計がどのように組み立つかが見えます。
| bit | 1の個数 | 0の個数 | 異なる組 | 寄与 |
|---|---|---|---|---|
| bit 0 | 2（1, 3） | 1（2） | 2 × 1 = 2 |
2 × 20 = 2 |
| bit 1 | 2（2, 3） | 1（1） | 2 × 1 = 2 |
2 × 21 = 4 |
| bit 2以上 | 0 | 3 | 0 | 0 |
寄与を足すと 2 + 4 = 6 です。これはABC147 D公式問題文のサンプル1の期待出力 6 と一致します。公式解説PDFでも、固定したbitで0と1から1つずつ選ぶ組が寄与すると説明されています。
ABC147 Dの完全Python参考コード
次のコードは、入力のNと値の列を読み、bit 0〜59を順に調べます。各bitの ones を数え、zeros = n - ones として寄与を加え、各段階で 109 + 7 の余りを取ります。ABC147 Dの公式の問題文と解説をPythonへ書き下した参考コードです。
import sys
MOD = 10**9 + 7
def main():
data = list(map(int, sys.stdin.buffer.read().split()))
n = data[0]
values = data[1:]
answer = 0
for bit in range(60):
ones = sum((value >> bit) & 1 for value in values)
zeros = n - ones
answer = (answer + ones * zeros * (1 << bit)) % MOD
print(answer)
if __name__ == "__main__":
main()value >> bit で対象bitを一番右へ移し、& 1 でそのbitだけを取り出します。これを全ての値で数えるため、ones が固定したbitの1の個数になります。
コード中の & と << はHTMLで表示するためにエスケープしています。実行時にはそれぞれPythonの & と << として解釈される文字です。
このコードが正しい理由
固定したbit k では、2つの値のk bitが異なる場合にだけXORのk bitが1になります。したがって、1のグループから1個、0のグループから1個を選ぶ ones × zeros 個の組だけが、そのbitへ寄与します。各組は i < j の1組として一度だけ数えられるので、寄与は ones × zeros × 2k です。
XORは各bitの結果を重ね合わせて値になるため、bit 0〜59の寄与を全て足せば、全ての i < j に対する A_i XOR A_j の総和になります。最後に法 109 + 7 を取っても、求める余りは変わりません。
計算量と調べる範囲
各bitでN個の値を走査し、60bitを調べるため時間計算量は O(60N) です。これは一般の表記では O(N log max A_i) に対応し、公式制約 A_i < 260 のもとでは60回のbit走査になります。入力列 values を保持するため追加の空間計算量は O(N)、集計変数は O(1) です。
ABC147 Dの公式サンプルで照合する
次の3組は、公式問題文に掲載された入力と期待出力です。いずれもコードへ無加工で入力します。
入力例1（公式）
3
1 2 3期待出力
6入力例2（公式）
10
3 1 4 1 5 9 2 6 5 3期待出力
237入力例3（公式）
10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820期待出力
103715602公式サンプル1は上のbit追跡で6になることを確認できます。サンプル2と3は、同じコードを公式入力へそのまま与え、期待出力と照合する対象です。公式解説はABC147公式解説PDFで確認できます。
手法を選ぶ境界と次の一手
ABC246 Aのように、座標や値が対応関係の中で2回ずつ現れるなら、全体のXORが0になる式を先に書き、既知の値をXORして未知の値を残せます。負の座標が含まれても、同じ値の自己打ち消しという条件は変わりません。
一方、対応関係がなく、全ての組のXOR和を求めるなら、ABC147 Dのように目的を固定bitの寄与へ分解します。XORを一度累積するだけでは、全ペアの合計は求まりません。値の出現回数やbit別の寄与がこの形にならないときは、線形基底、更新構造、別の計数方法など、問題の条件に合う構造へ切り替えます。
次に解くときは、まずABC246 Aで「どの値が2回現れて消えるか」を一行の式にします。その後、ABC147 Dの公式サンプル1を 001, 010, 011 に書き換え、bit 0とbit 1の ones × zeros を計算してから、掲載したコードへ公式サンプル1〜3を入力します。未知値の復元と全ペアの計数は別の目的ですが、どちらもbitごとの独立性を、条件に合わせて使う練習になります。
