公式
コンテスト全体の解説 by evima
HintsA - AABCDDEFE
Hint 1
As implied by the problem name, a decimal notation of a beautiful integer can be written as AABCDDEFE using digits A, B, C, D, E, and F. Let us reduce the problem on beautiful integers to a problem on $6$-tuples (A,B,C,D,E,F).Hint 2
There are only $9\times 10^5$ $6$-tuples (A,B,C,D,E,F), so you can generate all of them within the time limit. Or, you can directly find just the $N$-th one.Editorial → https://atcoder.jp/contests/arc153/editorial/5520
B - Grid Rotations
Hint 1
The row to which a square goes only depends on the row it belongs to before the move. By separately considering rows and columns, the problem can be reduced to a problem on a one-dimensional array.Hint 2
For a one-dimensional array of length $N$, we are to consider the operation of reversing the $a$ terms to the left and $N-a$ to the right. If we see the beginning and end of the array as being adjacent, the operation keeps adjacency.Editorial → https://atcoder.jp/contests/arc153/editorial/5522
C - ± Increasing Sequence
Hint 1
Here are some $A$ for which the answer is No: $(1, -1)$, $(-1,-1,1,1)$, and $(1, 1, -1, 1, -1, -1)$.Hint 2
Let us introduce new variables $y_i = x_i - x_{i-1}$ ($2\leq i\leq N -1$). Rewrite the conditions on $x$ into conditions on $(x_1, y_2, y_3, \ldots, y_{N})$.Hint 3
The writer's solution branches according to whether $\sum_{i=1}^N A_i$ is $0$ or not before constructing a solution.Editorial → https://atcoder.jp/contests/arc153/editorial/5523
D - Sum of Sum of Digits
Hint 1
By considering each possible value for the ones digit of $x$, you can develop a DP solution that computes the answer for a sequence $A$ from the answer for sequences $A'$ with smaller values.Hint 2
The sequences to consider in the DP are just the ones obtained by adding to $\lfloor A_i / 10^k\rfloor$ the carry from the lower digit. How many possible patterns of carries from the lower digits are there?Hint 3
The problem can be solved by computing $\text{dp}[k][n]$ defined as follows in order: $\text{dp}[k][n]$ is the answer to the problem for a sequence obtained by adding $1$ to $\lfloor A_i / 10^k\rfloor$ of the $n$ elements with the greatest $A_i\bmod{10^k}$.Editorial → https://atcoder.jp/contests/arc153/editorial/5525
E - Deque Minimization
Hint 1
To obtain the optimal $Y$ from $X$, you should insert digits not greater than the first digit of $S$ at the beginning, and the rest at the end of $S$.Hint 2
You can solve the problem in a time complexity of $O(N^2)$ by computing the number $\text{dp}[L][R]$ of sequences of operations that yield the $L$-th through $R$-th characters of $Y$. Let us optimize this solution.Hint 3
You only have to compute the dp for $L$ corresponding to digits that are in ascending order from the beginning of $Y$. Also, the computation that yields $\text{dp}[L-1][-]$ from $\text{dp}[L][-]$ can be represented as taking cumulative sums. By representing the repetition of the operation as convolution with a sequence of binomial coefficients, you can combine the transitions for a part with the same digit.Editorial → https://atcoder.jp/contests/arc153/editorial/5526
F - Tri-Colored Paths
Hint 1
Let us examine the properties of a coloring that has all three colors but does not satisfy the condition.Hint 2
If a cycle has two or more colors, when is the condition violated?Hint 3
If every cycle is $1$-colored, all edges in each biconnected component have the same color, so you can take the block-cut tree to reduce the problem to one on a tree.Editorial → https://atcoder.jp/contests/arc153/editorial/5527
投稿日時:
最終更新: