AtCoder Beginner Contest 126

Updated:

AtCoder Beginner Contest 126

  • Review: 2020-05-16
  • Review: 2020-07-03

Source codes

Solutions

A - Changing a Character

If you are using Ruby, just do s[k - 1].downcase!.

If you are using C++ and GCC, execute s[k - 1] = s[k - 1] - 'A' + 'a'.

B - YYMM or MMYY

Solution

$2$ 桁ごとに区切って $a, b$ とする。それぞれ $1 \leq a, b \leq 12$ かどうかを判定する。

Caution

Don’t forget to check the lower bound $a, b \geq 1$.

C - Dice and Coin

Solution

$C[i] = $ サイコロで $i$ が出た時に得点が $K$ 点以上になるまで表を出し続けなければいけない回数

とし、 \[ cnt[i] = \sharp \{ 1 \leq j \leq N \mid C[j] = i \} \] とする。答えは \[ \frac{1}{N} \sum _ {i = 0} ^ {50} \frac{cnt[i]}{2 ^ i}. \] である。

ポイント

誤差がほぼ許されないので、安直な実装は危ない。よく考えるべきである。

D - Even Relation

解答

$0$-indexed とする。 $0$ を白で塗る。 DFS をしていき、距離が奇数の場合は両端を違う色で塗り、偶数の場合は両端を同じ色で塗ればよい。

解答の正当化

まず偶奇しか関係ないので $\mathbb{Z} / 2 \mathbb{Z}$ で距離を持っておけば良い。$v, w$ の距離を $d(v, w)$ とすると、 \[ d(v, w) = d(0, v) + d(0, w) - 2 d(0, \mathrm{lca}(v, w)) = d(0, v) + d(0, w) \] となる。よって $d(v, w) = 0$ のとき、 $d(0, v) = d(0, w) = 0$ or $1$ であるから、 $v$ と $w$ は同じ色で塗られている。

E - 1 or 2

解答

$\mathbb{Z} / 2\mathbb{Z}$ で考えれば十分である。 $A _ X + A _ Y + Z = 0$ ということは、 $(X, Y)$ の片方が決まればもう片方も決まるということである。つまり $(X _ i , Y _ i)$ を辺とするグラフを考えると、そのグラフのある頂点 $v$ について $A _ v$ の値が決まるとそこから連結されている全ての頂点の値が決まる。よって連結成分の個数が総コストである。これを求めるには普通に DFS すれば良い。または Union-Find でもよろしい。

発展問題

「入力に矛盾があったら -1 を出力せよ」の場合はどうなるか。まず連結成分の個数が総コストなのは変わりない。辺は $0$ と $1$ があるので、まず $1$ だけで二部グラフ判定問題にする。二部グラフになっていれば今度は $0$ を判定する。これで判定が可能である。

F - XOR Matching

解答

$0 \leq K < 2 ^ M$ である必要がある。それ以外は -1 が答えである。以下ではこれが充たされていると仮定する。

$M = 0$ のとき、答えは 0 0 である。 $M = 1$ かつ $K = 0$ のとき、答えは 0 0 1 1 である。他にもある。 $K = 1$ のとき、答えは -1 である。これらは入出力例で与えられている。

$M \geq 2$ の時は全て答えが存在する。その構成を述べる。 \[ A = [0, 1, \dots, K - 1, K + 1, \dots, 2^M - 1] \] とし、 $B = \mathop{rev}(A)$ とする。このとき $K, A, K, B$ が解答となる。まず \[ \bigoplus _ {i = 0} ^ {2^M - 1} i = 0 \] であるから、 \[ \bigoplus _ {i \in A} i = K \] が従う。よって $K, A, K$ の部分はうまくいっている。他の部分は $B = \mathop{rev}(A)$ より、 xor が打ち消しあってうまくいっている。

鍵となる定理

累積 xor は以下の値をとる。

\[ \bigoplus _ {i = 0} ^ N i = \begin{cases} N & N \% 4 = 0, \\
1 & N \% 4 = 1, \\
N \oplus 1 & N \% 4 = 2, \\
0 & N \% 4 = 3. \end{cases} \]

よって $M = 1, K = 1$ だけは今回の場合は構成できない。

ポイント

F の全探索プログラムが間違っていて、思いつかなかった。

Others

しばらく judge queue の重さとの戦いにもなるだろう。