AtCoder Beginner Contest 146
Updated:
- Review: 2020-06-08
Source codes
Solutions
A - Can’t Wait for Holiday
Use vector<string>.
B - ROT N
Use the following lambda function.
auto adv = [&](char x) {
int l{x - 'A'};
int r{(l + N) % 26};
return static_cast<char>('A' + r);
};
Don’t forget to cast int into char.
C - Buy an Integer
The function $f(n) = An + B d _ n$ is an increasing function. Thus we use binary search.
D - Coloring Edges on Tree
Solution
The number of needed colors is just the maximal degree of every vertex. Therefore, we use DFS.
E - Rem of Sum is Num
Observation
We determine when $(i, j]$ is good. We use partial sum. We think of the following condition: $(S _ j - S _ i) \% K = j - i$. This is not equivalent to $(S _ j - S _ i) \% K = (j - i) \% K$ but $(S _ j - S _ i) \% K = (j - i) \% K$ and $j - i < K$.
To simplify the equation, First we subtract each $A _ i$ by $1$. Then, the condition is $S _ j \% K - S _ i \%K = 0$ and $j - i < K$.
Solution
Thus we can solve this problem by two-pointers method. We possess the distribution of $S _ i$ for the recent $K - 2$ elements. Use map<ll, ll> M;.
F - Sugoroku
DP part
First we reverse $S$. We go to $0$ from $i$. We can calculate
$DP[i] = $ the minimum steps from $i$ to $0$
as follows.
Initial state
$DP[0] = 0$; otherwise $-1$.
Transition
For $i = 1, \dots, N$, if $S[i] = 1$, we set $DP[i] = \infty$. Otherwise,
\[
DP[i] = 1 + \min _ {1 \leq k \leq M} DP[i - k],
\]
where out-of-range will be $\infty$. If we have $DP[i] > \infty$, flush -1 to exit. This can be done by multiset<int> I in $O(\log M)$-time.
Don’t forget to reverse $DP$.
Or, we can use segment tree.
Solution
Suppose that we are now in $i$-th square. We can go to whatever square $j$ we like as long as $j - i \leq M$ and $DP[j] = DP[i] + 1$. To find the lexicographically smallest sequence, we choose the smallest $j$.
This is done in $O(N)$-time because the index we see is increasing.