Pythonで解くAtCoder ABC126

2019年5月19日に行われたAtCoder Beginner Contest 126 のPython3での実装例です。

A - Changing a Character

使用テクニック： str.lower()
str.lower() で指定された大文字を小文字に変換。Pythonは0-indexであることに注意。

B - YYMM or MMYY

使用テクニック： if-elif-else
与えられた文字列を前半2文字と後半2文字に分け、int型として変数 a, b に取得。
a, b に収納された数字が0または12より大きい場合は年 (YY)、1以上12以下の場合は年 (YY) と月 (MM)のどちらもあり得ます。

C - Dice and Coin

使用テクニック： 確率計算
ダイスの値ごとに条件を満たす確率を求めて積算。
while 文で各ダイスの値が K を超えるまで倍にする回数を求め、ダイスが特定の数字を出す確率 $\frac{1}{N}$ にかけて積算します。

D - Even Relation

使用テクニック： 木構造、幅優先探索 (BFS, Breadth First Search)
任意のノードから各ノードへの距離の偶奇が分かれば、その関係は他のどのノードを起点にしても変わりません。
そのため、ノード 1 を起点とした各ノードの距離を幅優先探索 (BFS) でリスト(dist) にメモしておき、最後に各ノードに対して偶奇判定を行います。

E - 1 or 2

使用テクニック： Union-Find
入力として与えられる $(X, Y, Z)$ は、 $Z$ の値に関わらず、 $X, Y$ のどちらかの数字が分かればもう一方の数字も導けます。

$Z$ が偶数なら、 $(X, Y) = (0, 0) \, or \, (1, 1)$
$Z$ が奇数なら、 $(X, Y) = (0, 1) \, or \, (1, 0)$

ここで、入力で与えられた $(X _ i, Y _ i)$ の間にエッジを持つ $N$ 頂点のグラフを考えます。エッジで結ばれた頂点は、そのうちの1つの数字が分かれば他の頂点の数字も導くことが出来ます。よって、このグラフの連結成分の数が求める答えとなります。

F - XOR Matching

使用テクニック： $xor$ （排他的論理和）
$xor$ （排他的論理和）には以下の特徴があります。

同じ整数同士の $xor \, (\oplus)$ は $0$ になる： $n \oplus n = 0$
任意の整数 $n$ と $0$ の $xor \, (\oplus)$ は $n$ になる： $n \oplus 0 = n$
$i$ が2以上のとき、 $0$ から $2 ^ {i}-1$ までの累積 $xor$ は $0$ になる： $0 \oplus 1 \oplus \cdots \oplus 2 ^ {i} - 1 = 0$

よって、整数 $K$ を除いた $0$ から $2 ^ {M}-1$ までを昇順に並べた数列 $a$ と降順に並べた数列 $b$ で整数 $K$ を挟んだ数列では、 $K$ 以外の整数を選んだ際には $K$ 以外の数字が打ち消しあい、 $a _ i = a _ j$ かつ $a _ i \neq K$ を満たす任意の $i, j$ について、 $a _ i$ から $a _ j$ までの累積 $xor$ は $K$ となります。

$a \, K \, b = 0, 1, 2, \cdots, K-1, K+1, \cdots, 2 ^ M-1, K, 2 ^ M -1, \cdots, K+1, K-1, \cdots, 1, 0$

この時、
$a _ i \oplus a _ {i+1} \oplus \cdots \oplus 2 ^ M-1 \oplus K \oplus 2 ^ M-1 \oplus \cdots \oplus a _ {j-1} \oplus a _ j = K \,\,\, \because (a _ i = a _ j, a _ {i+1} = a _ {j-1}, \cdots)$

また、上記の数列の最後にも $K$ を追加することで、 $a _ i = a _ j = K$ の場合でも、 $a _ i$ から $a _ j$ までの累積 $xor$ は $K$ となります。

$a \, K \, b \, K = 0, 1, 2, \cdots, K-1, K+1, \cdots, 2 ^ M-1, K, 2 ^ M -1, \cdots, K+1, K-1, \cdots, 1, 0, K$

この時、はじめの $K$ から最後の $K$ までの累積 $xor$ は、
$K \oplus 2 ^ M - 1 \oplus 2 ^ M-2 \oplus \cdots \oplus K+1 \oplus K-1 \oplus \cdots \oplus 0 \oplus K = 0 \oplus 1 \oplus \cdots \oplus 2 ^ M-1 \oplus K$
となり、 $K \leqq 2 ^ M-1$ の場合 $xor$ の特徴3からこれは $K$ となります。

以上より、数列 $a \, K \, b \, K$ は、 $a _ i = a _ j$ を満たす任意の $i, j$ について、 $a _ i$ から $a _ j$ までの累積 $xor$ は $K$ となる。ただし、以下のコーナーケースが存在します。

コーナーケース

$K > 2 ^ M-1$ のとき、 $2 ^ M-1$ 以下の整数をどのようにしても $K$ を作れないためは条件を満たす数列は存在しません。
の場合、の特徴3が成立しないため、上記の数列では条件を満たさない。そのため、個別に処理する必要があります。
- $M = 0$ の場合、 $K = 0$ のみが許容され数列 $0, 0$ が答えとなります。
- $M = 1, K = 0$ の場合、入力例 1 が答えとなります。
- $M = 1, K = 1$ の場合、入力例 2 の通り条件を満たす数列は存在しません。