XOR構成ページの位置づけ
| 項目 | 内容 |
|---|---|
| 必修度 | 発展 |
| 学習目安 | 発展 |
| 前提 | XOR・構成 |
| 対象問題 | 3問（推定値あり3問、未算出0問） |
この記事のdifficulty区分は、問題を解く順番を決めるための目安です。AtCoderの公式なA〜F区分ではなく、取得できたdifficulty推定値を次の範囲に分けています。
| 学習目安 | difficulty推定値 | 問題数 |
|---|---|---|
| 入門 | difficulty < 0 | 1 |
| 標準 | 0〜799 | 1 |
| 標準〜発展 | 800〜1199 | 0 |
| 発展 | 1200以上 | 1 |
| 未算出 | — | 0 |
XORの性質から、条件を満たす数列を出力する形を直接組み立てます。存在しない境界を先に切り分けるのが要点です。
問題ごとの細かな実装は異なりますが、最初に確認する条件は共通しています。
XOR構成の見分け方
- XORの値が全体の条件を決める
- 値の集合を反転・除外して並べられる
- 出力列そのものが答えになる
XOR構成の実装前チェック
- 小さいMを全列挙して存在条件を確認する
- 特殊ケースを一般式から分ける
- 出力長と重複の有無を確認する
先に確認する文法・ライブラリ
まずは必須Python文法で、入力・配列・条件分岐・ループなどの基本を確認してください。問題に合わせたキュー、ヒープ、二分探索などの選び方は標準ライブラリ・定石にまとめています。
代表問題で実装を確認する
最初の一問として、ABC213 A Bitwise Exclusive Or（公式解説）を解きます。XORは同じ値を2回適用すると元に戻るため、A XOR B XOR B = Aです。AとBのXORを取れば、A XOR X = BとなるXを求められます。
A, B = map(int, input().split())
print(A ^ B)ビット数をWとするとO(W)時間・O(1)メモリです。
XOR構成の学ぶ順番
このページでは全件を一度に並べず、difficultyの推定値を目安に代表問題を段階分けしています。難易度が未算出の問題は、制約と出題意図を先に確認します。
まず解く
| 問題 | 公式解説 | 出題意図 | difficulty |
|---|---|---|---|
| ABC213 A Bitwise Exclusive Or | 公式解説 | A xor C=Bを満たすCはA xor BであるというXORの自己逆性を使う。 | -600 |
| ABC171 E Red Scarf | 公式解説 | 全要素のXORを求め、各要素を除いたXORは全体XORと自身のXORで復元できる性質を使う。 | 778 |
| ABC126 F XOR Matching | 公式解説 | XOR条件を満たす列を、除外する値と反転列の構造から直接構成する。 | 1770 |
問題文を読んだら、まず「見分け方」のどれに当たるかを一行で記録します。当てはまらない問題は、別のページへ移す判断自体を復習材料にします。
