AtCoder Beginner Contest 154
Updated:
- 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.
- Copy $(ni, nj, nk) \gets (i, j, k)$ first.
- Set $DP[ni][nj][nk] \mathbin { {+} {=} } DP[i][j][k]$ in the end.
- 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}. \]