AtCoder Beginner Contest 154

Updated:

AtCoder Beginner Contest 154

  • Review: 2020-06-17

Source codes

Solutions

A - Remaining Balls

If $S = U$, flush $A - 1, B$, otherwise $A, B - 1$.

B - I miss you…

Flush string T(S.size(), 'x');.

C - Distinct or Not

Use set<int> S;.

D - Dice in Line

Assume $0$-indexed. Let $q[i] = p[i] + 1$ and $S[i] = \sum _ {j \in i} q[j]$. The answer is \[ \frac{1}{2} \max _ {i + K \leq N} \left( S[i + K] - S[i] \right). \]

E - Almost Everywhere Zero

Solution

This is a typical problem about digit-DP. We possess the original $N$ by string $S$. Let $N = \lvert S \rvert$.

Definition

$DP[i][j][0] =$ how many possibilities there are regarding $[0, i)$-th digit with $j$ zeros, not being determined less than $N$ yet.
$DP[i][j][1] =$ how many possibilities there are regarding $[0, i)$-th digit with $j$ zeros, being already determined less than $N$.

Initial State

$DP[0][0][0] = 1$. Otherwise, $0$.

Answer

$DP[N][K][0] + DP[N][K][1]$.

Snuke’s digit-DP

Snuke’s digit-DP is a way of implementing digit-DPs.

  1. Copy $(ni, nj, nk) \gets (i, j, k)$ first.
  2. Set $DP[ni][nj][nk] \mathbin { {+} {=} } DP[i][j][k]$ in the end.
  3. Write the transition.
  for (auto i = 0; i < N; ++i)
  {
    for (auto j = 0; j <= K; ++j)
    {
      for (auto k = 0; k < 2; ++k)
      {
        for (auto d = 0; d <= 9; ++d)
        {
          int ni{i + 1}, nj{j}, nk{k}; // basic arrow, copy
          // Transition
          DP[ni][nj][nk] += DP[i][j][k];
        }
      }
    }
  }

Transition is written as follows.

          if (d > 0) // if we don't use d,
          {
            ++nj; // add 1
          }
          if (nj > K)
          {
            continue;
          }
          int num{S[i] - '0'};
          if (k == 0)
          {
            if (d > num) // violate the law less than or equal to N
            {
              continue;
            }
            if (d < num) // k: 0 -> 1
            {
              nk = 1;
            }
          }

Similar problem

F - Many Many Paths

Solution

Let $g(R, C)$ be the result $[0, R) \times [0, C)$. The answer is \[ g(R _ 2, C _ 2) - g(R _ 2, C _ 1 - 1) - g(R _ 1 - 1, C _ 2) + g(R _ 1 - 1, C _ 1 - 1). \]

Here, we have \[ g(R, C) = \sum _ {0 \leq i \leq R} \sum _ {0 \leq j \leq C} f(i, j). \] We use the well-known formula to have. \[ g(R, C) = \sum _ {0 \leq i \leq R} f(i + 1, C) = f(R + 1, C + 1) - f(0, C + 1) = f(R + 1, C + 1) - 1. \] And we know that \[ f(R + 1, C + 1) = \begin{pmatrix} R + C + 2 \\ R + 1 \end{pmatrix}. \]

Others