# AtCoder Beginner Contest 150

Updated:

AtCoder Beginner Contest 150

• Review: 2020-06-16

# 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$. It is needed that $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$.

### Another Solution

By $X = a _ i’ (2p + 1)$, we see that $X$ is a common multiple of $\{ a _ i’ \}$. Let $L$ be the LCM of $\{ a _ i’ \}$. $X$ is a multiple of $L$.

If there exists such $i \in N$ that $L / a _ i’$ is even, $X / a _ i’$ is even, which is a contradiction. In this case, the answer is $0$. Suppose that, for all $i \in N$, $L / a _ i’$ is odd. Then, we write $X = kL$ to see that $k$ is odd. We count this $k$ by auto K{M / L}; and auto ans{(K + 1) / 2};.

## 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. Without loss of generalities, we assume that $\{ C _ i \}$ is in the ascending order. We can see that we should always change $1$ into $0$ in the ascending order of $i$.

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 resolved 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 this $1$. For $j$-th digit for $j > i$, we count the half for the sum of these $1$s: $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)$ as the counts for the $C _ i$. 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})(\exists k \in N)(\forall i \in N)(a _ {i + k} \oplus x = b _ i). \tag{F.1}$ This is equivalent to the following condition. $(\exists k \in N)(\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$. We have $a _ {k + 1} \oplus b _ 1 = (a _ {k + 1} \oplus a _ k \oplus b _ 1 \oplus b _ 0) \oplus (a _ k \oplus b _ 0) = a _ k \oplus b _ 0,$ which implies (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 $(\exists k \in N)(\forall i \in N)(A _ {i + k} = B _ i). \tag{F.3}$ Then, (F.3) means that we find $B$ in $AA$ starting by the $k$-th element. This can be done by some good string search algorithm, such as KMP algorithm.

### Implement

We create $B$ and $AA$ and execute pop_back() once for $AA$. We create $B$’s MP array. Then, search $AA$ for $B$. When we find $k$, let $x = a _ k \oplus b _ 0$ and flush the answer.

# Others

Review 2020-06-16:

A - sample: 3, tle: 2.000, time: 02:22, from_submit: 48:42
B - sample: 3, tle: 2.000, time: 01:19, from_submit: 47:23
C - sample: 3, tle: 2.000, time: 03:49, from_submit: 43:34
D - sample: 3, tle: 2.000, time: 13:20, from_submit: 30:13
E - sample: 3, tle: 2.000, time: 12:52, from_submit: 17:21
F - sample: 4, tle: 2.000, time: 17:22, from_submit: 00:00


Tags:

Categories: