AtCoder Beginner Contest 138
Updated:
- Review: 2020-06-02
Source codes
Solutions
A - Red or Not
$a \geq 3200$ ならば $S$, そうでないなら red を出力する。
B - Resistors in Parallel
double 型で言われた通り計算する。
ポイント
AtCoder では std::scientific でも AC になるということをこの問題で初めて気が付いた。
C - Alchemist
解法
後のものほど大きなものが残るように、小さいものから貪欲に merge いくのが最善である。証明は通分すればできるがカット。
実装上のポイント
priority_queue を使う必要はない。小さいもの第 1 位・第 2 位を merge すれば、一番小さいものになる。
D - Ki
クエリを各頂点に持たせておく。あとは root から子に向かって dfs しておくと答えが出る。
ポイント
累積和の使い方を知っていれば問題ない。
E - Strings of Impurity
$X[i][j] = i$ 文字目からみて次に文字 $j$ が出てくるまでの距離
とする。これは後ろから 2 回ループを回して更新していけば構築可能である。あとは言われた通りにやるだけである。計算量は $O(\lvert S \rvert + \lvert T \rvert)$ である。
F - Coincidence
問題の言い換え
まず $x \leq y$ なる $(x, y) \in \mathbb{N}^2$ に対し、 \[ x \oplus y = y \% x \tag{F.1} \] となる条件を考察する。まず $x, y$ の最大 bit が違う場合、 $x \% y$ は最大 bit は立たない。一方で $x \oplus y$ は最大 bit が立つ。よってこの場合は条件は充たされない。よって $x, y$ の最大 bit は一致する。このとき $y \% x = y - x$ である。
ここで $x \oplus y$ と $x + y$ について比較をすると、両方の bit が立っている桁だけが異なることがわかる。つまり一般に次式が成立する。
\[
x + y = x \oplus y + 2 (x \land y). \tag{F.2}
\]
したがって (F.1) は次式と同値である。
\[
\begin{align}
x + y - 2(x \land y) &= y - x, \\
\Longleftrightarrow x &= x \land y, \\
\Longleftrightarrow x &\subset y.
\end{align}
\]
逆にこの条件から $x \leq y$ は勝手に出てくる。以上より、求めるものは以下の条件を全て充たす $(x, y)$ の組の個数である。
- $x \subset y$,
- $(x, y)$ の最大 bit が $(1, 1)$,
- $L \leq x$,
- $y \leq R$.
桁 DP
すぬけ式桁 DP をする。
まず $x \subset y$ とは、次にくる数字の組が $(0, 0)$ or $(0, 1)$ or $(1, 1)$ のどれかであるということである。これは遷移をこの $3$ つに絞ればいい。
次に $(x, y)$ の最大 bit が $(1, 1)$ という条件は、最大 bit が始まっているかどうかを bool key で持てば良い。「これまで $(0, 0)$ しか続いていない or $(1, 1)$ がきて始まっている」。
最後に $L \leq x$ と $y \leq R$ は、それぞれ bool key で管理できる。前者は「 $L \leq x$ が確定していない or $L < x$ が確定している」である。後者も類比的である。
定義
$dp[i][j][k][l] = i$ 桁目まで上から順番に見ていった時の場合の数。ただし $j = 0$ の時は $x \geq L$ が未確定であり、 $j = 1$ の時は $x > L$ が確定している。 $l = 0$ の時は $y \leq R$ が未確定であり、 $l = 1$ の時は $y < R$ が確定している。 $k = 0$ の時は最大 bit がまだスタートしていないが、 $k = 1$ の時は最大 bit がスタートしている。
初期状態
$dp[60][0][0][0] = 1$, otherwise $0$.
答え
$\sum _ j \sum _ k \sum _ l dp[0][j][k][l]$.
遷移
$i = 59, 58, \dots, 0$ に対し、 $j, k, l \in 2$ に対し、それぞれの遷移 $n, m \in 2$ を考察する。 $n$ は $x$ に次に続く桁、 $m$ は $y$ に次に続く桁である。
まず $(ni, nj, nk, nl) = (i, j, k, l)$ とする。 $pre = dp[i + 1][j][k][l]$ として、
\[
dp[ni][nj][nk][nl] \mathbin{ {+} {=} } pre
\]
とする方針とする。ここで $(ni, nj, nk, nl)$ を調整し、時には continue; することで、正しい答えとする。
- $j = 0$ のとき： $L \leq x$ が確定していないのに $L$ の $i$ 桁目が $1$ で $n = 0$ だと破綻する。これは
continue;である。また、$L$ の $i$ 桁目が $0$ で $n = 1$ だと $L < x$ が確定するので、この場合は $nj \gets 1$ とする。 - $l = 0$ のとき： $y \leq R$ が確定していないのに $R$ の $i$ 桁目が $0$ で $m = 0$ だと破綻する。これは
continue;である。また、$R$ の $i$ 桁目が $1$ で $n = 0$ だと $y < R$ が確定するので、この場合は $nl \gets 1$ とする。 - $k = 0$ のとき： $m = n = 1$ のとき、ここからはじまるので $nk \gets 1$ とする。そうでない場合は、 $m = n = 0$ 以外は、冒頭の条件に反するので、
continue;である。
Others
F の実装は大変参考になった。