AtCoder Beginner Contest 138

Updated:

AtCoder Beginner Contest 138

  • 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 の実装は大変参考になった。