競プロ参戦記 #46 XOR Matching | ABC 126

今週も AtCoder のプログラミングコンテストに参加しました。

ABC-only 回ですが、今回からシステムが変わって、レート変動の対象がレート **1999以下** (青コーダー以下) まで拡大しました。私も対象です。 **追記: [Unrated になりました。](https://twitter.com/atcoder/status/1130130313366200320)**

## AtCoder Beginner Contest 126

- この連載記事では、着手した問題の考察を自分なりに書いていきます。
    - 前回: [競プロ参戦記 #45 DivRem Number | diverta 2019 - Qiita](https://qiita.com/vain0x/items/fd9854b5863f1634dd04)
- 問題の詳細は問題一覧を参照してください。
    - 問題一覧: https://atcoder.jp/contests/abc126/tasks

## A - Changing a Character

問題概要: A, B, C のいずれかの文字からなる長さ N の文字列 S と、1 以上 N 以下の整数 K が与えられる。S の K 番目の文字を小文字に置き換えた文字列を出力せよ。

考察:

Rust では、標準ライブラリに [char::make_ascii_lowercase](https://doc.rust-lang.org/std/primitive.char.html#method.make_ascii_lowercase) という関数があるので、これを使えばいいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc126/submissions/5456485

## B - YYMM or MMYY

問題概要: 4つの数字が与えられる。これが YYMM 形式の日付としてありうるか、MMYY 形式の日付としてありうるかをそれぞれ判定せよ。

考察:

入力例を見ると、要するに MM の部分が 1 以上 12 以下であるかを判定すればいいようです。

したがって、まず4つの数字を2桁ずつの整数 a, b に分けて、次の2つの判定を行います。

- b が 1 以上 12 以下なら YYMM はありうる
- a が 1 以上 12 以下なら MMYY はありうる

そして、これらの結果の組み合わせ4通り (TT/TF/FT/FF) で場合分けして、適切な単語を出力します。スペルミスに注意しましょう。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc126/submissions/5454681

## C - Dice and Coin

問題概要: N 面サイコロを1回振って、その出目をスコアとる。表が出続ける限りコインを投げて、表が出るたびにスコアを2倍にする。最終的に、スコアが K 以上になるまで表が出続ければ勝ちである。このゲームの勝率を求めよ。

考察:

入力例を見るとほとんど解法に近い考え方が載っていますね。

- サイコロの出目を全通り試す
- 「スコアが K を超えるまでに何回連続で表を出し続けなければいけないか」の最小値 h を計算する
- このサイコロの出目における勝率は 1/2^h である

サイコロの出目ごとに排反なので、各出目における勝率の和を N で割った確率が答えとなります。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc126/submissions/5452745

## D - Even Relation

問題概要: N 頂点の木が与えられる。i 番目の辺は頂点 u, v の間を距離 w で繋いでいる。以下の条件を満たすように各頂点を白または黒で塗り分ける。塗り分けは必ず存在するので、一例を示せ。

条件: どの同色の2頂点も、その間の距離の総和が偶数である

考察:

すべての辺が w = 1 のケースを考えると、2部グラフの塗り分けをすればいいことが分かります。

他のケースも同様で、根からの距離の偶奇で塗り分ければよさそうです。

試しに2頂点 u, v を考え、それらの最低共通祖先を a とします。「u-v 間の距離が偶数」と「r-a-u の距離と r-a-v の距離の偶奇が等しい」が同値であればよいです。

```
      r (根)
      |
      a (共通祖先)
     /  \
    u    v
```

「r-a-u の距離と r-a-v の距離の偶奇が等しい」は「a-u の距離と a-v の距離の偶奇が等しい」と同値で、これは u-v (= u-a + a-v) の距離が偶数になることと同値です。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc126/submissions/5460076

## E - 1 or 2

問題概要: N 枚のカードが伏せられている。i 番目のカードには整数 A(i) (= 1 または 2) が書かれている。以下の M 個の条件が与えられているとき、すべてのカードに書かれた整数を特定するには、最小で何枚のカードをめくればよいか。

- i 個目の条件: 整数 X(i), Y(i), Z(i) が与えられて、A(X(i)) + A(Y(i)) + Z(i) が偶数であること

考察:

カードの数字は偶奇だけ考えればよいです。条件は、2枚のカード X(i), Y(i) の偶奇が等しいか否かを表していると解釈できます。

例えば2枚のカードがあって、偶奇が等しいと分かっているとします。このとき、1枚のカードをめくれば、他方のカードの数字も分かるので、答えは1になります。

もう少し複雑な状況として、3枚のカード x, y, z の偶奇が x = y, y != z というのを考えます。このときも1枚だけめくればいいです。x → y → z と **連鎖的に偶奇が決まる** からです。

結局、カードを点、カードの間の条件を辺としたグラフを考えて、その連結成分の個数が答えとなります。(Z を使わないのが妙ですね。)

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc126/submissions/5464673

## F - XOR Matching

問題概要: 非負整数 M (≤17) と非負整数 K (≤10^9) が与えられる。以下の条件を満たす長さ 2^(M+1) の数列 A が存在するか判定し、存在するなら一例を示せ。

条件:

- A は 0 以上 2^M 未満の各整数を、ちょうど2つずつ含む
- A(i) = A(j) (i < j) を満たす任意の区間につき、A(i) ^ A(i + 1) ^ .. ^ A(j) = K である

### 考察

いわゆる構築問題です。

例えば M=2, K=3 なら、数列の長さは 2^3 = 8 で、2^2 = 4 未満の各非負整数を2個ずつ含みます。実験してみると、以下の解が見つかりました。

```
    0 1 2 0 3 2 1 3
    ^^^^^^^
```

2つの 0 の間の区間 (ここでは 0-0 区間と呼びます) の xor は確かに K=3 になっています。他の数について確認しても、以下の通り、区間上の xor の値は 3 になっています。

```
    0 1 2 0 3 2 1 3
      ^^^^^^^^^^^

    0 1 2 0 3 2 1 3
        ^^^^^^^

    0 1 2 0 3 2 1 3
            ^^^^^^^
```

区間の両端は等しいという条件があるので、区間の内側の xor だけ見ればいいです。このことから、以下のような形の区間は xor の値が中央の値 K に一致することに気づくかもしれません……

```
    3 2 1 K 1 2 3
```

やや天下り的な考察ですが、このアイディアから一般解が導けます。M > 1 かつ 0 < K < 2^M なら、以下のような数列が解の一例です。

```
    0 K 0 2^M-1 .. 2 1 K 1 2 .. 2^M-1
          ^^^^^^^^^^^^   ^^^^^^^^^^^^
              K以外           K以外
```

0-0 の区間の xor は明らかに K ですし、それ以外の値の xor は右側にある K 以外がすべてキャンセルされる形で K になります。

問題は K-K の区間です。これは 0 から 2^M - 1 までの整数の xor が 0 になることから、この区間の xor は K だと分かります。(ただし後述の通り、M=1 のときだけ 0 になる。)

### エッジケース: K = 0

K = 0 のときは、入力例1にある通り、以下が解です。

```
    0 0 1 1 2 2 .. 2^M-1 2^M-1
```

すべての区間が長さ 2 で、両端はキャンセルされるので、xor の値が K = 0 になっています。

### エッジケース: K が巨大

K > 2^M のケースでは、K には数列上の要素にないビットが立っているので、どのような xor のとり方をしても「区間上の xor の値」が K になることはありません。区間は少なくとも1つ存在するので、解がないといえます。

### エッジケース: M が小さいケース

入力例 2 の M=1, K=1 はエッジケースです。上記の方法で構築すると以下の数列になりますが、これは 1-1 区間の xor が 0 になってしまうのでダメです。

```
    0 1 0 1
```

M=0 のときは K=0 か K ≥ 2^M のパターンが当てはまります。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/abc126/submissions/5479285