AtCoder Beginner Contest 146

Updated:

AtCoder Beginner Contest 146

  • 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.

Others