Official
Overall Editorial
by
ヒント集
Overall Editorial
by 
maspy
ヒント集
A - Repdigit Number
Hint 1
$10^N$ 未満の正整数で，$X$ を $10$ 進法表記をしたときのどの桁の数字も同じであるようなものは，全部でいくつあるでしょうか？Hint 2
$10^N$ 未満の正整数で，$X$ を $10$ 進法表記をしたときのどの桁の数字も同じであるようなものは，$9N$ 個です．これらすべてに対して $M$ で割った余りを計算しましょう．Hint 3
$n$ 桁の場合の余りは，$n-1$ 桁の場合の余りを利用すると $O(1)$ 時間で計算できます．解説 → https://atcoder.jp/contests/arc149/editorial/4869
B - Two LIS Sum
Hint 1
前提知識として，$N$ 項からなる数列の LIS は $O(N\log N)$ 時間で計算でき，これを本問題でも用います．Hint 2
隣接する組 $(A_i, B_i)$ をスワップできるということは，$N$ 個の組 $(A_i, B_i)$ を自由に並べ替えることができます．まずは両方の $A_i$, $B_i$ がともに LIS に使われるような組の集合を固定したときに，最適な並べ方が満たす性質を考えてみましょう．Hint 3
最適解において，任意の $i$ に対し $A_i, B_i$ のうち少なくとも一方は LIS の項として使われることを証明できます．さらに，$A$ が昇順に並んでいるような最適解が存在することも証明できます．解説 → https://atcoder.jp/contests/arc149/editorial/4910
C - Avoid Prime Sum
Hint 1
$4$ 以上の偶数は素数ではありません．Hint 2
マス目の上半分に奇数，下半分に偶数を書き込むことで，大部分の隣接する $2$ 数の和を $4$ 以上の偶数にすることができます．Hint 3
マス目の上半分に奇数，下半分に偶数を書き込むことにします．奇数と偶数が隣接する部分が必ず $6$ 以上の $3$ の倍数になるようにすれば目標を達成できます．解説 → https://atcoder.jp/contests/arc149/editorial/4911
D - Simultaneous Sugoroku
Hint 1
すべての出発位置 $1, 2, \ldots, 10^6$ にコマが置かれているとして，すべてのコマの結果を求めましょう．Hint 2
ある時点で座標が $x$, $-x$ であるような $2$ つのコマについて，片方のコマの結果からもう片方のコマの結果が分かることを利用します．Hint 3
ある時点で座標が $x$, $-x$ であるような $2$ つのコマについて，片方だけをシミュレーションしていき，もう片方はその結果から答を求めることにします．計算が必要なコマを $x>0, x<0$ の片側にまとめると次の座標変化が場合分けなく記述できます．Hint 4
参考画像
解説 → https://atcoder.jp/contests/arc149/editorial/4902
E - Sliding Window Sort
Hint 1
ソートされる区間が移動するのが少し分かりにくいです．ソート区間の位置を固定して，列を cyclic shift していく問題に言い換えた方が扱いやすいと思います．Hint 2
$K$ がとても大きい場合，数列の変化はかなり単純な規則になります．具体的な数列で実験することも有効だと思います．Hint 3
本問題は $M+K-1=N$ の場合に帰着できます．解説 → https://atcoder.jp/contests/arc149/editorial/4912
F - Rational Number System
Hint 1
展開の一意存在は，$r^0$ の位から順に考えることで証明できます．$n$ の $r$ 進法展開の prefix が別の数の $r$ 進法展開であることも分かります．Hint 2
文字列集合の辞書順は，Trie を dfs したときの preorder と一致します．Hint 3
Trie における，subtree の頂点数などを計算することができれば $L, \ldots, R$ 番目の頂点を高速に探索できます．同じ深さを持つ頂点をまとめて数えましょう．
posted:
last update: