AtCoder Beginner Contest 138

Updated:

AtCoder Beginner Contest 138

ソースコード

解法のメモ

A - Red or Not

$a \geq 3200$ ならば $S$, そうでないなら red を出力する。

B - Resistors in Parallel

double 型で言われた通り計算する。

ポイント

AtCoder では std::scientific でも AC になるということをこの問題で初めて気が付いた。

C - Alchemist

後のものほど大きなものが残るように、貪欲に取っていくのが最善である。

ポイント

証明は通分すればできるがカット。

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$ は勝手に出てくる。以上より、求めるものは $L \leq x$ かつ $y \leq R$ かつ $x, y$ の最大 bit が等しいかつ $x \subset y$ を充たす $(x, y) \in \mathbb{N}^2$ の個数である。

桁 DP

管理する数字が $2$ つある桁 DP をする。まず $x \subset y$ とは、次にくる数字の組が $(0, 0)$ or $(0, 1)$ or $(1, 1)$ のどれかであるということである。これは遷移をこの $3$ つに絞ればいい。次に「 $x, y$ の最大 bit が等しい」については bool key を持つことで実装できる。つまり「まだ始まっていない」 or 「すでに始まっている」で実装できる。最後に $L \leq x$, $y \leq R$ については「確定している」 or 「未確定」で場合分けすればよろしい。

$dp[i][j][k][s] = i$ 桁目まで上から順番にみていった時の場合の数。ただし $j = 0$ の時は $x \geq L$ が未確定であり、 $j = 1$ の時は $x > L$ が確定している。 $j = 0$ の時は $y \leq R$ が未確定であり、 $j = 1$ の時は $y < R$ が確定している。 $s = 0$ の時は最大 bit がまだスタートしていないが、 $s = 1$ の時は最大 bit がスタートしている。

初期状態 $dp[60][0][0][0] = 1$, otherwise $0$. 答え $\sum _ j \sum _ k \sum _ s dp[0][j][k][s]$. 遷移は複雑であるので以下の通りに考察する。

$i = 59, 58, \dots, 0$ に対し、各 $(j, k, s) \in 2 ^ 3$ に対し、 $(x, y) \in 2 ^ 2$ に対し、新しい $(nj, nk, ns) \in 2 ^ 3$ を構築することにし、そこに \[ dp[i][nj][nk][ns] \mathbin{ {+} {=} } dp[i + 1][j][k][s] \tag{F.3} \] とする方針でいく。基本的にはまず $(nj, nk, ns) \gets (j, k, s)$ とコピーしておく。このとき問題文の $x, y$ に今の $(x, y) \in 2 ^ 2$ を続けることにする。先ほど述べたとおり $(x, y) = (1, 0)$ の場合 continue; する。その他の条件は以下の通り。

  • $s = 0 \land ((x, y) = (1, 0) \lor (0, 1))$ の場合: continue;,
  • $(x, y) = (1, 1)$ の場合: $ns \gets 1$,
  • $j = 0 \land x = 0 \land L[i] = 1$ の場合: continue;,
  • $x = 1 \land L[i] = 0$ の場合: $nj \gets 1$,
  • $k = 0 \land y = 1 \land R[i] = 0$ の場合: continue;,
  • $y = 0 \land R[i] = 1$ の場合: $nk \gets 1$.

実装

今書いた通りに実装すればよろしい。

  for (auto i = 60 - 1; i >= 0; i--)
  {
    int lb = L >> i & 1;
    int rb = R >> i & 1;
    for (auto j = 0; j < 2; j++) // j = 0: x \geq L が未確定。 j = 1: x > L が確定。
    {
      for (auto k = 0; k < 2; k++) // k = 0 : k \leq R が未確定。 k = 1: y < R が確定。
      {
        for (auto s = 0; s < 2; s++) // s = 0: 始まっていない。 s = 1: 始まっている。
        {
          mint pre{dp[i + 1][j][k][s]}; // 前の状態。
          for (auto x = 0; x < 2; x++)
          {
            for (auto y = 0; y < 2; y++)
            {
              if (x && !y) // x = 1, y = 0 はアウト。
              {
                continue;
              }
              int nj{j}, nk{k}, ns{s}; // 次の状態を計算して足しこむ。
              if (!s && x != y)        // 始まっていないのに (1, 0) or (0, 1) はアウト。
              {
                continue;
              }
              if (x && y) // (1, 1) の場合は、すでに始まっているか、ここから始まる。
              {
                ns = 1;
              }
              if (!j && !x && lb) // x \geq L が未確定なのに x = 0, lb = 1 はアウト。
              {
                continue;
              }
              if (x && !lb) // x = 1, lb = 0 の場合は x > L が確定する。
              {
                nj = 1;
              }
              if (!k && y && !rb) // y \leq R が未確定なのに y = 1, rb = 0 はアウト。
              {
                continue;
              }
              if (!y && rb) // y = 0, lb = 1 の場合は y < R が確定する。
              {
                nk = 1;
              }
              dp[i][nj][nk][ns] += pre;
            }
          }
        }
      }
    }
  }

ポイント

管理する数字が $2$ つあるので、複雑であるが、難しくはない。

  • 基本的にはまず $(nj, nk, ns) \gets (j, k, s)$ とコピーしておく。
  • (F.3) を目指す。

その他

F の実装は大変参考になった。