AtCoder Beginner Contest 156

Updated:

AtCoder Beginner Contest 156

Source codes

Solutions

A - Beginner

Flush $R + 100(10 - \min(N, 10))$

B - Digits

Use while loop.

C - Rally

Try all $0 \leq X \leq 100$. Or we can try just two possibility as follows. We want to minimize \[ f(X) = \sum _ {i \in N} (X _ i - X) ^ 2. \] Note that $f$ is a quadratic function. If $X$ is real valued, the minimum is achieved at $X$ with $f’(X) = 0$, i.e., \[ X = \frac{1}{N} \sum _ {i \in N} X _ i. \] Therefore, we try $X = \sum X _ i / N$ and $(\sum X _ i / N) + 1$ where / is computer’s division.

D - Bouquet

The answer is \[ 2 ^ N - 1 - \begin{pmatrix} N \\ A \end{pmatrix} - \begin{pmatrix} N \\ B \end{pmatrix}. \]

Here, $N \leq 10 ^ 9$. We should use the following formula. \[ \begin{pmatrix} N \\ A \end{pmatrix} = \frac{N!}{A! (N - A)!} = \frac{N \cdot (N - 1) \cdot \dots \cdot (N - A + 1)}{A!} \] We can calculate the right hand side’s denominator in $O(A)$.

E - Roaming

Let $V$ be the array of the numbers of people in each room. First, we determine that we can make it for given $V$. Thanks to the condition $N \geq 3$ and $K \geq 2$, we can say that $V$ is possible if and only if there are less than or equal to $K$ rooms where no people are present.

Thus we fix the number of the empty rooms $x$. We choose $x$ rooms of $N$ rooms as the empty rooms. After that, we distribute $x$ people to $N - x$ rooms. Therefore, the answer is \[ \sum _ {0 \leq x \leq K} \begin{pmatrix} N \\ x \end{pmatrix} \begin{pmatrix} x + N - x - 1 \\ N - x - 1 \end{pmatrix}. \]

F - Modularness

If we answer each query in $O(K)$, this problem is solved. That is, we generate the function ll solve(ll n, ll x, ll m).

Let $e _ i = d _ i \% m$ and $x \gets x \% m$. We use $X, Y, Z$ to denote the followings.

$X = $ the number of $0 \leq i \leq n - 1$ that satisfies $a _ i < a _ {i + 1}$,
$Y = $ the number of $0 \leq i \leq n - 1$ that satisfies $a _ i = a _ {i + 1}$,
$Z = $ the number of $0 \leq i \leq n - 1$ that satisfies $a _ i > a _ {i + 1}$.

Apparently, we see that $X + Y + Z = N - 1$. We want to calculate $X$, but instead of that, we count up $Y$ and $Z$.

We see that $Y$ is the number of $i$ which satisfies $e _ i = 0$. And we come up with a good idea that we consider $Z$ as the number of carrying-up. We don’t need to determine where it occurs. To compute the count, we just divide $x$ plus the sum of $e _ i$ by $m$.

Both of these ideas are compatible to the period. Let $S = \sum _ {i \in k} e _ i$. Let $C$ be the number of $i \in k$ with $e _ i = 0$. Let $T = (n - 1) / k$ be the number of the reputation of rotation of $e$. Let $U = (n - 1) \% k$ be the the remainder. Let $A$ be $x$ plus the sum of $e _ i$. Then, we can compute as follows. \[ \begin{align} A &= x + ST + \sum _ {i < U} e _ i, \\\ Y &= CT + \sum _ {i < U} \delta _ {e _ i = 0}, \\\ Z &= A / m. \end{align} \] The answer is $X = n - 1 - Y - Z$.

Others