AtCoder Beginner Contest 172
Updated:
Source codes
Solutions
A - Calc
Flush $a + a ^ 2 + a ^ 3$.
B - Minor Change
Let $N$ be the length of $S$ or $T$. For $i = 0, \dots, N - 1$, if $S[i] = T[i]$, increment the count. Flush the result.
C - Tsundoku
Assume $0$-indexed. This is not a greedy simulation problem, but a cumulated sum problem.
Let $sumA$ and $sumB$ be the cumulated sum of $A$ and $B$, respectively. For $i = 0, \dots, N$, let $L = K - sumA[i]$. If $L < 0$, continue. Let $j = $ upper_bound(sumB.begin(), sumB.end(), L) - sum.begin() $- 1$. Here, $i + j$ is a possible number of books we can read. This is valid because $sumB$ is strictly increasing since $B _ i > 0$.
D - Sum of Divisors
Solution #1: $O(N \log N)$
Let $cnt[i] = $ be the number of divisors of $i$. We can obtain the result in the same way of Sieve of Eratosthenes. Then, calculate $\sum _ {i = 1} ^ N i \times cnt[i]$. The time complexity is $O(N \log N)$.
Solution #2: $O(N)$
This problem can be directly implemented as follows.
ll ans{0};
for (auto i{1}; i <= N; ++i)
{
for (auto j{1}; j <= N; ++j)
{
if (i % j == 0)
{
ans += i;
}
}
}
return ans;
We can swap the loop. If we swap $i$’s loop and $j$’s loop, we see that this problem is equivalent to the task that for each $j = 1, \dots, N$, we add up the sum $j, 2j, \dots, (N / j) * j$. This sum is calculated as follows. \[ j \times \frac{(N / j) ((N / j) + 1)}{2}. \] Hence, the total complexity is $O(N)$.
E - NEQ
Assume $0$-indexed.
Solution
This is an inclusive-exclusive principle problem.
The second condition is equivalent to that we don’t use each number more than twice. If $M < N$, the answer is $0$.
For $x \subset N$, we think of the number of placement for $(A, B)$ where it holds that $A _ i = B _ i$ for $i \in x$ (It may or may not hold $A _ i \neq B _ i$ for each $i \in N \setminus x$). This number is effected only by $\lvert x \rvert$. Thus, let $K = 0, \dots, N$ and let $f(K)$ be the number of placement for $(A, B)$ with this condition. The answer is \[ \sum _ {K = 0} ^ N (-1) ^ K \begin{pmatrix} N \\ K \end{pmatrix} f(K). \]
We choose $K$ elements from $N$ for the $i \in N$ with $A _ i = B _ i$. We choose $K$ numbers from $M$ for $A _ i = B _ i$. This is $M! / (M - K)!$. From the remaining elements, we choose $(N - K)$ elements for $A$ and $B$ independently. This is $((M - K)! / (M - N)!) ^ 2$. Then, we have \[ f(K) = \frac{M!}{(M - K)!} \left( \frac{(M - K)!}{(M - N)!} \right) ^ 2. \]
F - Unfair Nim
Solution
Let $A’ = A _ 1$, $B’ = A _ 2$ and $C = \bigoplus _ {i = 3} ^ N A _ i$. Let $A$ and $B$ be the results. Let $S = A’ + B’$. The condition is
\[
\begin{align}
A + B &= S, \tag{F.1} \\
A \oplus B &= C, \tag{F.2} \\
0 < A &\leq A’. \tag{F.3}
\end{align}
\]
Here $A + B = A \oplus B + 2 (A \land B)$. Letting $D = (S - C) / 2$, we see that (F.1) is equivalent to the following condition.
\[
A \land B = D. \tag{F.4}
\]
Of course, we have to check $S - C \geq 0$ and $(S - C) \% 2 = 0$ before that.
To consider (F.2) and (F.4), we think of $a \oplus b$ and $a \land b$ with $0 \leq a, b \leq 1$ as follows.
| $(a, b)$ | $a \oplus b$ | $a \land b$ |
|---|---|---|
| $(0, 0)$ | $0$ | $0$ |
| $(1, 0)$ | $1$ | $0$ |
| $(0, 1)$ | $1$ | $0$ |
| $(1, 1)$ | $0$ | $1$ |
There is no possibility for $(a, b)$ with $a \oplus b = a \land b = 1$. Therefore, if $C \land D \neq 0$, the answer is negative. Hereinafter, assume $C \land D = 0$. Then, for each $i$ with $D[i] = 1$, we must have $A[i] = 1$. For each $i$ with $C[i] = 1$, we have choice that we let $A[i] = 0$ or $1$. Thus, temporality, we let $A = D$.
We maximize $A$ with (F.3). We apply a greedy algorithm for this. We try $i$ with $C[i] = 1$ in descending order. If $A + (C[i] \mathbin{< <} i) \leq K$, we execute $A \gets A + (C[i] \mathbin{< <} i)$. Finally, we confirm (F.3) and flush $A’ - A$.