AtCoder Beginner Contest 156
Updated:
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)}{1 \cdot 2 \cdot \dots \cdot A} \] We can calculate the right hand side’s denominator in $O(A)$.
E - Roaming
If $K \geq N$, any distribution is possible. The answer is \[ \begin{pmatrix} N + (N - 1) \\ N - 1 \end{pmatrix}. \]
Hereinafter, we assume that $K < N$. 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
A - sample: 2, tle: 2.000, time: 03:10, from_submit: 36:07
B - sample: 3, tle: 2.000, time: 01:06, from_submit: 35:01
C - sample: 2, tle: 2.000, time: 02:52, from_submit: 32:09
D - sample: 2, tle: 2.000, time: 03:39, from_submit: 28:30
E - sample: 3, tle: 2.000, time: 07:56, from_submit: 00:00
F - sample: 2, tle: 2.000, time: 23:15, from_submit: 01:15