AtCoder Beginner Contest 162
Updated:
Source codes
Solutions
A - Lucky 7
We get the input as a string. We check whether there exists $i \in 3$ so that $S[i] == $ ‘7’.
B - FizzBuzz Sum
Do as they indicate us to.
C - Sum of gcd of Tuples (Easy)
For $a, b, c \in \mathbb{N}$, it holds that \[ \gcd(a, b, c) = \gcd(\gcd(a, b), c). \] We can obtain the answer by direct calculation.
D - RGB Triplets
Solution
This problem has two conditions.
- (i) $S[i], S[j], S[k]$ are different color from each other.
- (ii) $k \neq 2j - i$.
For (i), the number of the possible tuples is $rgb$, where $r$, $g$ and $b$ denotes the number of the red, green and blue balls, respectively.
From this, we subtract the number of the tuples that satisfies (i) but not (ii). For $0 \leq i < j < N$, let $k = 2j - i$. If $k \geq N$, continue. Then, we check if this $(i, j, k)$ satisfies (i) or not.
E - Sum of gcd of Tuples (Hard)
Solution
We set $f$ as follows.
$f(X) = $ the number of the tuples $\{ A _ i \}$ whose $\gcd$ is $X$.
Then, The answer is \[ \sum _ {X = 1} ^ K f(X) X. \tag{E.1} \]
We introduce a helper function.
$g(X) = $ the number of the tuples $\{ A _ i \}$ where $X$ divides $\{ A _ i \}$.
Let $1 \leq X \leq K$. Fix $\{ A _ i \} _ {i \in N}$. The condition that $X$ divides $\gcd \{ A _ i \}$ is, for all $i \in N$, $X$ divides $A _ i$. Since $1 \leq A _ i \leq K$, this number is easily calculated as follows. \[ g(X) = \left( \frac{K}{X} \right) ^ N. \tag{E.2} \] Here the division is computational division.
We can calculate $f(X)$ in descending order. This is because \[ f(X) = g(X) - f(2X) - f(3X) - \dots = g(X) - \sum _ {j \geq 2} f(jX). \tag{E.3} \]
Combining (E.2) and (E.3), we can calculate (E.1) in $O(K \log K)$-time.
F - Select Half
Assume $0$-indexed.
Observation
Consider the case where $N$ is even. We decide which $A[i]$ to take from left to right. Then, we notice that, to take $N / 2$ elements, we take exactly $1$ extra margin before we reach the right side. We can solve this case by some cumulated sums in $O(N)$.
Then, consider the case where $N$ is odd. By same argument, we take exactly $2$ extra margins. In this case, direct calculation does not work since it would take $O(N ^ 2)$-time.
Thinking of this problem carefully, we can forget the old details since extra margins can be at most $2$. Therefore, we overcome this difficulty by DP.
DP part
Definition
$dp[i][j] = $ the answer of the subtask $A[0, i)$, i.e., the maximum of the sum, with the current extra margins is $j$.
Initial state
$dp[0][0] = 0$. Otherwise, $- \infty$.
Answer
$dp[N][K]$, where $K = 1$ if $N$ is even and $K = 2$ if $N$ is odd.
Transition
The idea of this transition is a little bit difficult. Consider the case that we fix $j = 0$. We take $A[i]$ if $i$ is even, i.e., $i \% 2 = 0$. If we change $j = 0$ into $1$, we take $A[i]$ if $i$ is odd after that. Therefore, the parity of $(i + j)$ plays an important role.
Then, we summarize the transition as follows. For $i = 0, 1, \dots, N - 1$, for $j = 0, 1, 2$, we execute the following.
\[
\begin{align}
dp[i + 1][j + 1] &\gets ^ {\min} dp[i][j], \tag{F.1} \\
dp[i + 1][j] &\gets ^ {\min}
\begin{cases}
dp[i][j] + A[i] & (i + j) \% 2 = 0, \\
dp[i][j] & (i + j) \% 2 = 1,
\end{cases} \tag{F.2}
\end{align}
\]
Here, (F.1) means that we have an extra margin at $i$-th grid and (F.2) means the normal skip and normal taking.