AtCoder Beginner Contest 126
Updated:
- 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 の重さとの戦いにもなるだろう。