AtCoder Beginner Contest 150

Updated:

AtCoder Beginner Contest 150

Solutions

A - 500 Yen Coins

Flush “Yes” if $500K \geq X$ or “No” otherwise.

B - Count ABC

Use substr to get the substrings of $S$.

C - Count Order

Use next_permutation to enumerate all possibilities of the permutations.

D - Semi Common Multiple

Note

We have a constraint that all $a _ i$ are even. But this is actually not guaranteed at the contest.

Solution

If there exists an odd $a _ i$, the answer is $0$. Suppose that all $a _ i$ are even. Let $a _ i’ = a _ i / 2$. We have $X = a _ i’ (2p + 1)$. Let $f(x)$ be the function that presents how many times we can divide $x$ by $2$. We have $f(X) = f(a _ i’)$; otherwise the answer is $0$. Suppose that all $f(a _ i’)$ are the same. We use $t$ to denote this number. Let $a _ i’’ = a _ i’ / 2 ^ t$ and $X’ = X / 2 ^ t$. Then $X’$, $a _ i’’$ and $2p + 1$ are all odd numbers with $X’ = a _ i’’ (2p + 1)$. Let $L = \mathrm{lcm}(a’’ _ i)$. Then, we have $X’ = L \times (\text{odd number})$ and this presents all possibilities. The answer is $(M’ + 2L - 1) / 2L$, where $M’ = M / 2 ^ t$.

E - Change a Little Bit

Solution

Suppose that we fix $S = 00 \dots 0$. Then we find that the answer will be $2 ^ N$ times. We assume without loss of generalities that $\{ C _ i \}$ is in ascending order. We can see that we always should change $1$ into $0$ ion ascending order.

How many times do we add $C _ i$? We can say that when we consider changing $1$ to $0$ on the $i$-th digit, we have solved the $j$-th digit for $0 \leq j < i$. The final count will be $2 ^ i$ times. Then, on the $i$-th digit, we always solve the conflict. Thus we count $2 ^ {N - 1 - i}$ times. For $j$-th digit for $j > i$, we count the half: $2 ^{N - 1 - i - 1}$. Thus we have $2 ^ i (2 ^ {N - 1 - i} + (N - 1 - i) 2 ^ {N - 1 - i - 1} ) = 2^{N - 2} (N - i + 1)$ counts. Therefore the answer is $2 ^ N \sum _ {i = 0} ^ {N - 1} 2^{N - 2} (N - i + 1) C _ i = 4 ^ {N - 1} \sum _ {i = 0} ^{N - 1} C _ i (N - i + 1).$

F - Xor Shift

Observation

We work on the condition $(\exists x \in \mathbb{N})(\forall i \in N)(a _ {i + k} \oplus x = b _ i). \tag{F.1}$ This is equivalent to the following condition. $(\forall i \in N)(a _ {i + k} \oplus a _ {i + k + 1} = b _ i \oplus b _ {i + 1}). \tag{F.2}$ We can see this equivalence as follows. Suppose we have (F.1). Then (F.2) follows immediately. Suppose we have (F.2). Then we set $x = a _ k \oplus b _ 0$ to have (F.1).

Let $a _ i’ = a _ i \oplus a _ {i + 1}$ and $b _ i’ = b _ i \oplus b _ {i + 1}$. Then, (F.2) is equivalent to $(\forall i \in N)(a _ {i + k}’ = b _ i’). \tag{F.3}$ Then, (F.3) means that we find $A$ in $BB$ starting by the $k$-th element. This can be done by some good string search algorithm, such as KMP algorithm.

Implement

We create $A$ and $BB$. We create $A$’s MP array. Then, search $BB$ for $A$. When we find $l$, it will mean that $k = N - l$. Note that the cases $k = 0$ and $k = N$ are the same. Letting $x = a _ k \oplus b _ 0$, we flush the answer.

Tags:

Categories: