# AtCoder Beginner Contest 154

Updated:

AtCoder Beginner Contest 154

# 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;
}
}


## 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}.$

Tags:

Categories: