#A — Can't Wait for Holiday↵
↵
The only approach here is the trivial one--compare the input to each of the possible seven values and print the appropriate answer for each of them. One reasonably fast way to implement this is to create an array $A$ containing the seven inputs, with "SUN" in position zero and "SAT" in position six. Then, we compare $S$ to each value in the array and, upon finding the value $i$ such that $A[i] = S$, we print $7-i$. This is valid because the next Sunday after the day represented by our input would come in position seven.↵
↵
Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8604159)↵
↵
---↵
↵
#B — ROT N↵
↵
Again, the only real solution here is to directly implement the approach given in the problem statement. However, character arithmetic gives us a fairly nice way to do so. For each character in $S$, we can compute the position of the corresponding letter in the alphabet by taking $S[i]$ minus the character 'A'. From here, we can add $N$ to this value and take the result modulo $26$ to find the offset corresponding to our new letter upon ciphering. Then, we can add 'A' to the offset and set $S[i]$ to the result to update $S$ accordingly. Finally, we simply print $S$.↵
↵
Runtime: $O(N)$. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8605539)↵
↵
---↵
↵
#C — Buy an Integer↵
↵
Observe that we should buy a number with the greatest possible number of digits, since any number is strictly greater than any other number with fewer digits. We iterate over the possible numbers of digits in decreasing order and print our answer as soon as we find a number of digits at which we can afford some number.↵
↵
Given that we want to buy an $N$-digit number, the cheapest one is $10^{N-1}$, which will cost $10^{N-1}A + NB$. If this is greater than $X$, we must try a lower value of $N$. If not, let's solve for the maximum number we can buy. Suppose this number is $M$. Then, we must have $MA + NB \leq X$, so $MA \leq X - NB$, so $M \leq \frac{X - NB}{A}$. Thus, any $N$-digit number that is at most $\frac{X - NB}{A}$ will be cheap enough. Keep in mind that since we've assumed we're buying an $N$-digit number, $M$ must be at most $10^N - 1$, even if $\frac{X - NB}{A}$ is $10^N$ or greater. (For example, if $A = 1$, $B = 20$, and $X = 40$, then we clearly cannot buy any number with at least two digits, and when we consider one digit, we find $\frac{X - NB}{A} = 20$. However, since we're only considering one-digit numbers, the greatest possible answer is $9$.)↵
↵
From here, we can iterate over all possible values of $N$ in decreasing order and print the answer corresponding to the first sufficiently cheap value of $N$. It's probably a good idea to check separately whether we can buy $10^9$, since this case works a little differently because we can't buy any larger $10$-digit numbers. ↵
↵
Runtime: $O(\log MX)$, where $MX$ is the greatest integer sold. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8612652). ↵
↵
---↵
↵
#D — Coloring Edges on Tree↵
↵
We claim $K$ is the maximum degree of any edge. Our construction is fairly simple. Root the tree at vertex $1$ and perform a DFS. Then, when we reach a node $v$, color its children edges with any set of colors from $1$ to $K$ not already used to color the edge from $v$ to its parent, if $v$ isn't the root. This will always be possible because we know by our choice of $K$ that there will be at least $\textrm{deg} \, v$ colors to choose from, so we can use the colors $1$ through $\textrm{deg} \, v$ for this, possibly excluding the one already used for the edge from $v$ to $v$'s parents. In practice, my solution iterates through the colors starting with $1$ and skipping the one already used if necessary.↵
↵
Proving that no answer lower than this $K$ is possible is fairly trivial. Suppose for contradiction that $\textrm{deg} \, v$ is greater than the minimum possible $K$ for some vertex $v$. Then, by the Pigeonhole Principle, it is impossible to color the edges incident to $v$ with different colors from $1$ to $K$, so this must not be the case. Therefore, $K$ must be at least $\textrm{deg} \, v$ for all vertices on the graph, which implies that our solution is optimal.↵
↵
Runtime: $O(N)$. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8610136)↵
↵
---↵
↵
#E — Rem of Sum is Num↵
↵
First, note that the required conditions cannot hold for a sequence of at least $K$ elements, since any value $K$ or greater cannot be the remainder when our sum is divided by $K$. Otherwise, we can write the given equation for the range $i$ through $j$ as↵
↵
$$\sum_{k = i}^j A_k - 1 = 0 \, \textrm{mod} \, K.$$↵
↵
We thus decrease all values in the array by $1$, reducing our problem to counting subarrays summing to $0 \, \textrm{mod} \, K$ with length less than $K$. This can be solved using prefix sums and a sliding window. First, ignore the condition on the length of $K$. Then, the number of valid sequences ending at $j$ is the number of earlier positions $i$ such that↵
↵
$$\sum_{k = 0}^i A_k - 1 = \sum_{k = 0}^j A_k - 1,$$↵
↵
working modulo $K$. We can iterate over all prefixes of the array and maintain a map from prefix sums modulo $K$ to the number of times they've occurred so far to keep count of this. Then, to bring back the condition on the length of our array, we can remove the sum that occurred $K$ positions earlier from our map before incrementing the answer at each position so that at any given time, all subarrays of length $K$ or greater are not considered as options.↵
↵
Runtime: $O(N \log N)$. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8612198)↵
↵
---↵
↵
#F — Sugoroku↵
↵
We employ dynamic programming. Let $dp[i]$ be the minimum number of moves to reach cell $N$ from cell $i$, and let $nxt[i]$ be the least possible next move from position $i$ that makes it possible to achieve this minimum. We can compute $dp[i]$ for all positions except the game-over cells as one plus the minimum of $dp[i+j]$ over all $j$ from $1$ to $M$, and $nxt[i]$ is the least $j$ that achieves this minimum. (For simplicity, we let $dp[i]$ be infinity for all game-over cells.)↵
↵
Of course, implementing this as given would take $O(NM)$ time, so we need to be faster about it. There are lots of ways to do this--for example, we could use a segment tree. However, my solution employs a priority queue. The queue will store pairs $(dp[i], i)$ and will be sorted such that the lowest element is that with the lowest value of $dp[i]$, with ties broken by selecting the lowest value of $i$ (in order to satisfy lexicographic minimality), since at any given point we should transition to the smallest possible next point. Then, we iterate over all positions in decreasing order of $i$. To compute $dp[i]$, we first check the top element $(dp[j], j)$ from the queue and, while this top element has $j > i+M$, pop it from the queue, since we can no longer make a move that will get us far enough to reach this position. Then, if any elements remain in the queue, we can set $dp[i]$ to $dp[j] + 1$ and $nxt[i]$ to $j-i$. If no elements remain in the queue, it is impossible to reach the end of the board from position $i$.↵
↵
From here, we can print $-1$ if $dp[0]$ is infinity. Otherwise, we can reconstruct and print the answer using the $nxt$ array. ↵
↵
Runtime: $O(N \log N)$. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8614378)↵
↵
---↵
↵
As always, questions and comments are welcome below.
↵
The only approach here is the trivial one--compare the input to each of the possible seven values and print the appropriate answer for each of them. One reasonably fast way to implement this is to create an array $A$ containing the seven inputs, with "SUN" in position zero and "SAT" in position six. Then, we compare $S$ to each value in the array and, upon finding the value $i$ such that $A[i] = S$, we print $7-i$. This is valid because the next Sunday after the day represented by our input would come in position seven.↵
↵
Runtime: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8604159)↵
↵
---↵
↵
#B — ROT N↵
↵
Again, the only real solution here is to directly implement the approach given in the problem statement. However, character arithmetic gives us a fairly nice way to do so. For each character in $S$, we can compute the position of the corresponding letter in the alphabet by taking $S[i]$ minus the character 'A'. From here, we can add $N$ to this value and take the result modulo $26$ to find the offset corresponding to our new letter upon ciphering. Then, we can add 'A' to the offset and set $S[i]$ to the result to update $S$ accordingly. Finally, we simply print $S$.↵
↵
Runtime: $O(N)$. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8605539)↵
↵
---↵
↵
#C — Buy an Integer↵
↵
Observe that we should buy a number with the greatest possible number of digits, since any number is strictly greater than any other number with fewer digits. We iterate over the possible numbers of digits in decreasing order and print our answer as soon as we find a number of digits at which we can afford some number.↵
↵
Given that we want to buy an $N$-digit number, the cheapest one is $10^{N-1}$, which will cost $10^{N-1}A + NB$. If this is greater than $X$, we must try a lower value of $N$. If not, let's solve for the maximum number we can buy. Suppose this number is $M$. Then, we must have $MA + NB \leq X$, so $MA \leq X - NB$, so $M \leq \frac{X - NB}{A}$. Thus, any $N$-digit number that is at most $\frac{X - NB}{A}$ will be cheap enough. Keep in mind that since we've assumed we're buying an $N$-digit number, $M$ must be at most $10^N - 1$, even if $\frac{X - NB}{A}$ is $10^N$ or greater. (For example, if $A = 1$, $B = 20$, and $X = 40$, then we clearly cannot buy any number with at least two digits, and when we consider one digit, we find $\frac{X - NB}{A} = 20$. However, since we're only considering one-digit numbers, the greatest possible answer is $9$.)↵
↵
From here, we can iterate over all possible values of $N$ in decreasing order and print the answer corresponding to the first sufficiently cheap value of $N$. It's probably a good idea to check separately whether we can buy $10^9$, since this case works a little differently because we can't buy any larger $10$-digit numbers. ↵
↵
Runtime: $O(\log MX)$, where $MX$ is the greatest integer sold. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8612652). ↵
↵
---↵
↵
#D — Coloring Edges on Tree↵
↵
We claim $K$ is the maximum degree of any edge. Our construction is fairly simple. Root the tree at vertex $1$ and perform a DFS. Then, when we reach a node $v$, color its children edges with any set of colors from $1$ to $K$ not already used to color the edge from $v$ to its parent, if $v$ isn't the root. This will always be possible because we know by our choice of $K$ that there will be at least $\textrm{deg} \, v$ colors to choose from, so we can use the colors $1$ through $\textrm{deg} \, v$ for this, possibly excluding the one already used for the edge from $v$ to $v$'s parents. In practice, my solution iterates through the colors starting with $1$ and skipping the one already used if necessary.↵
↵
Proving that no answer lower than this $K$ is possible is fairly trivial. Suppose for contradiction that $\textrm{deg} \, v$ is greater than the minimum possible $K$ for some vertex $v$. Then, by the Pigeonhole Principle, it is impossible to color the edges incident to $v$ with different colors from $1$ to $K$, so this must not be the case. Therefore, $K$ must be at least $\textrm{deg} \, v$ for all vertices on the graph, which implies that our solution is optimal.↵
↵
Runtime: $O(N)$. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8610136)↵
↵
---↵
↵
#E — Rem of Sum is Num↵
↵
First, note that the required conditions cannot hold for a sequence of at least $K$ elements, since any value $K$ or greater cannot be the remainder when our sum is divided by $K$. Otherwise, we can write the given equation for the range $i$ through $j$ as↵
↵
$$\sum_{k = i}^j A_k - 1 = 0 \, \textrm{mod} \, K.$$↵
↵
We thus decrease all values in the array by $1$, reducing our problem to counting subarrays summing to $0 \, \textrm{mod} \, K$ with length less than $K$. This can be solved using prefix sums and a sliding window. First, ignore the condition on the length of $K$. Then, the number of valid sequences ending at $j$ is the number of earlier positions $i$ such that↵
↵
$$\sum_{k = 0}^i A_k - 1 = \sum_{k = 0}^j A_k - 1,$$↵
↵
working modulo $K$. We can iterate over all prefixes of the array and maintain a map from prefix sums modulo $K$ to the number of times they've occurred so far to keep count of this. Then, to bring back the condition on the length of our array, we can remove the sum that occurred $K$ positions earlier from our map before incrementing the answer at each position so that at any given time, all subarrays of length $K$ or greater are not considered as options.↵
↵
Runtime: $O(N \log N)$. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8612198)↵
↵
---↵
↵
#F — Sugoroku↵
↵
We employ dynamic programming. Let $dp[i]$ be the minimum number of moves to reach cell $N$ from cell $i$, and let $nxt[i]$ be the least possible next move from position $i$ that makes it possible to achieve this minimum. We can compute $dp[i]$ for all positions except the game-over cells as one plus the minimum of $dp[i+j]$ over all $j$ from $1$ to $M$, and $nxt[i]$ is the least $j$ that achieves this minimum. (For simplicity, we let $dp[i]$ be infinity for all game-over cells.)↵
↵
Of course, implementing this as given would take $O(NM)$ time, so we need to be faster about it. There are lots of ways to do this--for example, we could use a segment tree. However, my solution employs a priority queue. The queue will store pairs $(dp[i], i)$ and will be sorted such that the lowest element is that with the lowest value of $dp[i]$, with ties broken by selecting the lowest value of $i$ (in order to satisfy lexicographic minimality), since at any given point we should transition to the smallest possible next point. Then, we iterate over all positions in decreasing order of $i$. To compute $dp[i]$, we first check the top element $(dp[j], j)$ from the queue and, while this top element has $j > i+M$, pop it from the queue, since we can no longer make a move that will get us far enough to reach this position. Then, if any elements remain in the queue, we can set $dp[i]$ to $dp[j] + 1$ and $nxt[i]$ to $j-i$. If no elements remain in the queue, it is impossible to reach the end of the board from position $i$.↵
↵
From here, we can print $-1$ if $dp[0]$ is infinity. Otherwise, we can reconstruct and print the answer using the $nxt$ array. ↵
↵
Runtime: $O(N \log N)$. [Click here for my submission.](https://atcoder.jp/contests/abc146/submissions/8614378)↵
↵
---↵
↵
As always, questions and comments are welcome below.
