AtCoder Beginner Contest 150
Updated:
- Review: 2020-06-16
Source codes
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