AtCoder Beginner Contest 161
Updated:
Source codes
Solutions
A - ABC Swap
Just swap as they indicate us to.
B - Popular Vote
Be careful when we calculate “$1 / 4M$of the total number of votes”. This should be done by ceiling function and check the condition “less than” that.
C - Replacing Integer
We continue to execute this manipulation while $x > K$. Then, the result is $N \% K$. After that, we execute this manipulation to get $N \% K$ and $K - N \% K$. We flush the minimum of that.
D - Lunlun Number
We can make a Lunlun numbers by recursion of the tail of the number. If $X$ is a Lunlun number and its tail is $k$, $10X + l$ is also a Lunlun number if $\lvert k - l \rvert \leq 1$.
This manipulation is order-preserving. Thus we can use queue<int> Q; to get $K$-th Lunlun number.
E - Yutori
Assume $1$-indexed.
Observation
Suppose that we are bound to work on $i$-th day. We think of $S[1, i - 1]$ and reversed version of $S[i + 1, N]$. For each schedules, how can we maximize the working day? Greedy algorithm works. This is because of the following reasons.
- Suppose that there is a schedule which is not greedily made. That is, we have a skipped day. If we take that day, the “refraining from working” term is backed, since the length of that is always $C$. Thus, the greedy algorithm always gives the best schedule.
- The reversed string also works, since the condition that after working for a day we will refrain from working on the subsequent is still valid in the reversed string.
Solution
We make the following tables. Their length is $N + 2$ with the indexes $0$ and $N + 1$ is sentinels.
vector<int>$X[i] = $ the maximum working days we can make during $S[1, i - 1]$,
vector<int>$Y$: reversed version of $X$ when $S$ is reversed. That is, $Y[i] = $ the maximum working days we can make during $S[i + 1, N]$.
For each $i \in [1, N]$ with $S[i] = $ o, Check the sum $X[i - 1] + Y[i + 1]$. However hard we may work, we can work in $X[i - 1] + Y[i + 1]$. Thus, if it is less than $K$, we cannot skip this day. Otherwise, we may skip this day to gain $K$ working days.
F - Division or Subtraction
Let $C = 10 ^ 6 + 10$.
Observation
Lemma F.1: In the original manipulation, divisions cannot come after subtractions.
Proof: Assume to the contrary that a division occurs after a subtraction. That is, \[ x (\text{subtraction}) \mapsto x - K (\text{division}) \mapsto (x - K) / K \] This means that $K$ cannot divide $x$ but $K$ can divide $(x - K)$. This is a contradiction.
Lemma F.2: The recursive application of the original operation is equivalent to the following operation.
- While $K$ divides $N$, replace $N$ with $N / K$. Then, we replace $N$ with $N \% K$.
Proof: The order of the divisions before the subtractions is followed by Lemma F.1. For the latter part, replacing $N$ with $N - K$ while $N \geq K$ result in $N \% K$.
Solution
We divide the problem into two cases: the case $K < C$ and the case $K \geq C$.
The case $K < C$
We can obtain the answer by direct simulation of the manipulation argued in Lemma F.2.
The case $K \geq C$
Again we divide this case into two sub-cases.
If $K$ divides $N$, the result $N / K$ is less than $K$ since $\sqrt{N} \leq 10 ^ 6 < C \leq K$. Then, the result is $1$ if and only if $N / K = 1$, i.e., we check whether $N \geq C$; if so, we add $1$ to the answer.
If $K$ cannot divide $N$, then, the result is $N \% K$. If it is $1$, this means that $K$ divides $N - 1$. Since $K > \sqrt{N}$, we try $K = N / i$ with $i = 1, \dots, C - 1$ being a divisor of $N$ to check $K \geq C$ and $K < N$.
Others
- 2020-06-22
A - sample: 3, tle: 2.000, time: 03:48, from_submit: 75:19
B - sample: 3, tle: 2.000, time: 04:57, from_submit: 27:18
C - sample: 3, tle: 2.000, time: 02:48, from_submit: 69:35
D - sample: 4, tle: 2.000, time: 12:29, from_submit: 57:06
E - sample: 4, tle: 2.000, time: 27:48, from_submit: 29:18
F - sample: 3, tle: 2.000, time: 27:18, from_submit: 00:00