AtCoder Beginner Contest 172

Updated:

AtCoder Beginner Contest 172

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

Tags:

Categories: