AtCoder Beginner Contest 162

Updated:

AtCoder Beginner Contest 162

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

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

Tags:

Categories: