763が考察の質・量で頭一つ抜けてる。763と780は(約2年を要して)solved数が最近ようやく100を超えたけど、763は純粋な難しさ由来としても780は考察すら諦めた人がほとんどじゃないかと思う。ただ解法を導くのはそこまで難しくなく、過大評価気味
400番台前半は今では(Eulerで)ド典型になっているやつもあって過大評価気味
494,566とかは他所でまず見れなさそうな問題で凄い
700番台以降とかは難易度は高いけど、ARCとか大学有志コンのボスとかでギリ出そうではある
「式変形してしまえばあっさり」的な問題が多く、やはり問題の見た目で惑わされずにしっかり手計算で考察することが一番重要

2023-06-22

Alien DP についてのメモ

競技プログラミングアルゴリズム AtCoder

Alien DPの自分なりの理解をメモ。

アルゴリズムの説明

$M = ( M_0, M_1, ..., M_n )$ を広義で上に凸であることがわかっている未知の数列とする。

与えられた $k$ に対して $M_k$ を求めることを目指す。

$a_i = M_{i+1}-M_i$ とおくと、 $M$ が広義で上に凸であることから $a_i$ は広義単調減少である。

この時関数 $f_i, g$ を $f_i(x) = -ix+M_i$ 、 $g(x) = \max\limits_{0 \leq j \leq n} f_j(x)$ で定義すると以下の補題が成り立つ。

補題

$x \in [a_i : a_{i-1} ]$ の時、 $g(x) = f_i(x)$ である。

(ただし便宜上 $a_{-1} = \infty, a_n = -\infty$ とする)

証明

$a_i \leq x \leq a_{i-1}$ として、 $0 \leq j \leq n$ に対し $f_j(x) \leq f_i(x)$ を示す。

$j \geq i$ の時と $j \leq i$ の時で場合分けする。

$j \geq i$ の時、

$$ \begin{aligned} f_i(x)-f_j(x) &= -ix+M_i+jx-M_j \\ &= (j-i)x-(M_j-M_i) \\ &= (j-i)x-(a_i+a_{i+1}+\ldots+a_{j-1}) \\ &\geq (j-i)x-(j-i)a_i \\ &= (j-i)(x-a_i) \\ &\geq 0 \end{aligned} $$

である。 $j \leq i$ の場合も同様。

(証明終)

上の補題から、全ての $0 \leq i \leq n$ に対して $g(x) = f_i(x)$ を満たす $x$ が存在することがわかる。

また、そのような $x$ が取りうる範囲 $[a_i : a_{i-1} ]$ は $i$ が増加するごとに負の方向に移動する。

したがって $0 \leq k \leq n$ が与えられた時、 $g(x) = f_k(x) = -kx+M_k$ となるような $x$ を求めれば、 $M_k = g(x)+kx$ で $M_k$ を求めることができる。

下の画像は $M= ( 0, 10, 14, 14, 9 )$ の時の $f_i(x), g(x)$ のイメージ。

補足

$x$ が与えられた時に $g(x)$ がそれなりの速度( $O(N)$ とか)で求められる必要がある。
競プロでは $M_k$ を「それぞれにスコアが与えられている何かの集合の中から(条件を満たしつつ) $k$ 個選んだ時のスコアの合計の最大値」のように定義した場合、すなわち
$M_k = \max\limits_{S \in {\cal S}, |S|=k} \sum\limits_{t \in S} c_t$
のような形の時、

$\begin{aligned} g(x) &= \max\limits_{0 \leq k \leq n} \left( -kx + \max\limits_{S \in {\cal S}, |S|=k} \sum\limits_{t \in S} c_t \right) \\ &= \max\limits_{0 \leq k \leq n} \max\limits_{S \in {\cal S}, |S|=k} \sum\limits_{t \in S} (c_t-x) \\ &= \max\limits_{S \in {\cal S}} \sum\limits_{t \in S} (c_t-x) \end{aligned}$

と変形でき、DPで $g(x)$ の値と、 $f_i(x)=g(x)$ となる $i$ の値が簡単に求まることがある。

上の議論より、 ${M_i}$ が全て整数ならば $g(x) = f_k(x) = -kx+M_k$ となるような整数 $x$ が存在することがわかる。
また、そのような $x$ を二分探索する範囲は $[a_{n-1} : a_0 ]$ を含むように取れば良い。*1
$x_0 = a_l = a_{l+1} = \ldots = a_{r-1}$ の場合、すなわち $M$ の傾きが $[l:r]$ で単調な場合、全ての $i \in [l:r]$ に対して $f_i(x)=g(x)$ となる。
後述の問題例のように「 $M_k \leq X$ を満たす最小の $k$ を求める」ような場合に注意が必要となる。
下に凸な場合は $f_i(x) = ix+M_i$ 、 $g(x) = \min\limits_{0 \leq j \leq n} f_j(x)$ とおく。