A. Changing a Character

小文字にする．解答例

B. YYMM or MMYY

YYが00のときも駄目だと思ってしまった（西暦の下2桁なので00があってもよい）．2桁ずつ取って，それが1以上12以下であれば月として使える．これを両方について試し，条件分岐すればよい． 解答例

C. Dice and Coin

ABCDEの中で一番困った． 解答例

$N$面サイコロの出目をすべて試す（出目を$v$とする）．このとき得点が$K$になる確率を調べたい．$K \le v$のときはサイコロを振った時点でゲームが終了するため，確率は$1$．$v \lt K$のときはコインを投げる必要がある．投げる回数を$i$とすると，$K \le v \times 2^{i}$となる最小の$i$を求めることになる．これは$\log$を用いて$\log_2 \frac {K} {v} \le i$と変形できるから，$i = \lceil \log_2 \frac {K} {v} \rceil$．従って確率は$\frac {1} {2^i}$．これを$v$について合計すればよい．

なおループで$i$を求めても間に合ったようだ．これはループ回数が先の$\lceil \log_2 \frac {K} {v} \rceil$であることから$O(N \log K)$となる．

D. Even Relation

図示するとよい． 解答例

まず奇数長の辺で結ばれた2つの頂点$p,q$は違う色でなければならない．このとき，その一端$q$からさらに繋がる点$r$について：

• 辺$(q,r)$の長さが奇数長：$q,r$は異なる色にする必要があるが，これは可能である（$(p,r)$の距離は偶数長であるから$p,r$を同じ色にしてよい）．
• 辺$(q,r)$の長さが偶数長：$(p,r)$の距離は奇数長になるから$p,r$は異なる色である必要がある．$p,q$と$p,r$がそれぞれ異なる色同士であるから，$q,r$は同じ色．

よって奇数長の辺の一つの端点を選び，そこから繋がる点について再帰的に「辺の長さが奇数長であれば前の頂点と異なる色，偶数長であれば同じ色を塗る」処理を行えばよい．すべての辺が偶数長の場合はどのように頂点を塗ってもよいため適当に頂点を選べばよい．さらにすべてが偶数長でなくとも適当に頂点を選んでよい（奇数長の辺に遭遇するまですべて同じ色で塗ることになるが，その結果は奇数長の辺から始めた場合と同一であるから）．

なお辺が偶数長であるときは本来両端に異なる色を塗ってもよいのだが，奇数長の辺が存在する場合失敗することがある．例えば辺$(1,2)$の長さが$1$，$(2,3)$の長さが$2$のとき，$2,3$に異なる色を塗ると$1,3$の色が等しくなるが，距離は$3$と奇数．

E. 1 or 2

解答例

まず$A _ {X _ i} + A _ {Y _ i} + Z_i$が偶数であることから，$A _ {X _ i} + A_{Y _ i}$の偶奇が分かる．ここで$A_i$がすべて$1$か$2$であることに注意すると，$A _ {X _ i}$の値が分かれば$A _ {Y _ i}$の値も偶奇性から分かる（！）．これは連鎖する：$A_p + A_q$と$A_q + A_r$の偶奇が分かっているとき，$A_p$の値が分かれば$A_q$の値が分かり，さらに$A_r$の値が分かる．

従ってこの関係を図示する，すなわち辺が各$(X_i,Y_i)$であるようなグラフを描けば，各連結成分について1つ値が分かりさえすれば残りの要素もすべて分かることになる．したがって連結成分の数が答えとなる．これはUnionFind（またはDFSなど）で調べられる．

F. XOR Matching

抽象的に区間の共通部分をうまく使う方法を考えていたが浮かばず．解説放送でも触れられていたが構築問題なので実験してみるべきだった． 解答例

解けなかった構築問題の記事をどう書けばいいかは難しいところだが，結論から言うと$K \le 2^M-1$のときに次のような形を作るとほとんどの場合でうまくいく（ただし$...$には$K$は含まれない）：

$$0,1,2,...,2^M-1,K,2^M-1,...,2,1,0,K$$

こうすると$K$以外の整数$v$同士が作る区間の共通部分をそのまま使い回せて（$v$同士のxorは$0$となるためxorが内側と等しくなる），その値は中央の$K$となる．$K$が作る区間については$K,...,2,1,0,K$となるが，このxorも実はほとんどの場合で$K$となる：

$a$の値が$2^M-1$までであることに注目すると，この区間は

$$K,2^M-1,2^M-2,...K+1,K-1,...,2,1,0,K$$

となり，xorは$K \oplus 2^M-1 \oplus ... \oplus 0$となる（順序を入れ替えることで$...$は$K$を含む）．これはABC121-D: XOR Worldでも出題されたように隣り合う偶数と奇数のxorが$1$になることを利用すれば$K \oplus 1 \oplus ... \oplus 1$となる．この$1$の個数は$2^M / 2$であり：

• $M = 0$のとき：
  • $1$の個数がバグるのでこの構築法は使えない．
  • 実際に試すと$a=\{0,0\}$しかない．よって$K=0$のみが存在．
• $M = 1$のとき：
  • $1$は$1$個．よってxorは$K \oplus 1$となる．これが$K$と等しいような数は存在しない（$K \oplus 1 = K$の両側に$K \oplus$を適用すれば$1 = 0$）．すなわちこの構築法は使えない．
  • 一方で，入出力例にもあるように$M=1$でも解を持つことがある．全探索で求めればよい．パターンは$\frac {4!} {2! 2!} = 6$通り，対称性を考慮すれば0011, 0101, 0110, 1001の$4$つであり，ここから$K=0$のときは複数の解が存在する一方で，$K \ge 1$のときは存在しないことが明らかになる．
• $M \ge 2$のとき：
  • $1$は$2^M / 2$個であるが，これは偶数．従ってxorは$K \oplus (1 \oplus ... \oplus 1)$ $= K \oplus (0 \oplus ... \oplus 0) = K$．
  • ゆえに確かに$K$同士の区間のxorも$K$となるから，この構築法が使える．

最後に$K \gt 2^M-1$の場合：このときは先の構築はできないが，$0$から$2^M - 1$までの数を適当に選んでxorで作れる値の最大値は$2^M-1$である（$2^M$に相当するビットが立っている数が存在しないため，いかなるxorの結果もこのビットを持たない，すなわち$2^M$以上にならない）から弾いてしまって問題ない．

結論：

• $K \le 2^M - 1$のとき
  • $M = 0$または$M = 1$のとき: 実際に試すと$K = 0$しかない
  • $M \ge 2$のとき: 構築法を用いると作れる
• $K \gt 2^M - 1$のとき: 作れない