Official
Overall Editorial
by
ヒント集
Overall Editorial
by 
maspy
ヒント集
A - AABCDDEFE
Hint 1
美しい整数の $10$ 進法表記は，問題タイトルのように $1$ 桁の数字 A,B,C,D,E,F を用いて AABCDDEFE と書けるものです．美しい整数に関する問題を，$6$ つ組 (A,B,C,D,E,F) に関する問題に帰着しましょう．Hint 2
$6$ つ組 (A,B,C,D,E,F) は $9\times 10^5$ 通りしかないので，実行制限時間内にその全てを生成することが可能です．また，$N$ 番目だけを直接求めることもできます．解説 → https://atcoder.jp/contests/arc153/editorial/5483
B - Grid Rotations
Hint 1
あるマスの移動先の行番号は，移動前の行番号だけから決まります．行番号だけ，列番号だけについての問題に分けて考えることで，本問題は $1$ 次元配列に関する問題に帰着できます．Hint 2
長さ $N$ の $1$ 次元配列について，「左 $a$ 個・右 $N-a$ 個のを逆順に並べ替える」という操作を考えることになります．列の先頭と末尾が隣接していると見なすことにすると，操作は隣接関係を保ちます．解説 → https://atcoder.jp/contests/arc153/editorial/5484
C - ± Increasing Sequence
Hint 1
答が No となる $A$ の例：$(1, -1)$, $(-1,-1,1,1)$, $(1, 1, -1, 1, -1, -1)$ など．Hint 2
新たに $y_i = x_i - x_{i-1}$ （$2\leq i\leq N -1$）という変数を導入します．$x$ に関する条件を，$(x_1, y_2, y_3, \ldots, y_{N})$ に関する条件に書き直してみましょう．Hint 3
writer 解では，$\sum_{i=1}^N A_i$ が $0$ であるか否かで場合分けをして解を構築しています．解説 → https://atcoder.jp/contests/arc153/editorial/5485
D - Sum of Sum of Digits
Hint 1
$x$ の $1$ の位で場合分けすることで，数列 $A$ に対する答を，より値の小さな数列 $A'$ に対する答から計算するというタイプの dp が考えられます．Hint 2
dp で考えるべき数列は，$\lfloor A_i / 10^k\rfloor$ に対して下位の桁からの繰り上がり分を加えてできる数列のみです．「下位の桁からの繰り上がり」としてはどのくらいのパターン数を考えればよいでしょうか．Hint 3
本問題は，次で定義される $\text{dp}[k][n]$ を順に計算することで解くことができます：$\lfloor A_i / 10^k\rfloor$ に対してさらに $A_i\bmod{10^k}$ が大きい方から $n$ 個の添字部分に $1$ を加えてできる数列を考え，その数列に対する問題の答を $\text{dp}[k][n]$ とする．解説 → https://atcoder.jp/contests/arc153/editorial/5486
E - Deque Minimization
Hint 1
$X$ から最適な $Y$ を得るには，$S$ の先頭以下の数字を先頭に，それ以外の数字を末尾に挿入するようにすればよいです．Hint 2
$Y$ の $L$ 文字目から $R$ 文字目までの部分に至る Hint 1 のような操作列の数え上げ $\text{dp}[L][R]$ を順に計算していくことで，時間計算量 $O(N^2)$ で解くことができます（$N$ は $Y$ の桁数）．これを高速化します．Hint 3
dp を計算すべき $L$ は，$Y$ の先頭から見て数字が昇順に並んでいる部分に限定できます．また，$\text{dp}[L][-]$ から$\text{dp}[L-1][-]$ を得る計算は，累積和をとる操作で表すことができます．累積和をとる操作の繰り返しを二項係数の列との畳み込みで表すことで，同じ数字が並ぶ部分の dp の遷移をまとめて計算できます．解説 → https://atcoder.jp/contests/arc153/editorial/5487
F - Tri-Colored Paths
Hint 1
$3$ 色すべての色が現れる塗り方のうちで，条件を満たさないものがどのようなものであるかを調べます．Hint 2
あるサイクルに $2$ 色以上が現れる場合，条件を満たさないのはどのようなときでしょうか？Hint 3
すべてのサイクルが $1$ 色からなる場合には，各二重連結成分内ではすべての辺の色が等しいので，block-cut tree をとって木の問題に帰着できます．
posted:
last update: