EDPC と TDPC の出題のうち、題意よりも強いか効率的な解法があるもの。
Educational DP Contest : (https://atcoder.jp/contests/dp)
Typical DP Contest : (https://atcoder.jp/contests/tdpc)
説明は詳細ではない。実装例および外部の出題、あるいは個別問題のユーザ解説(2024-05-25 追記)を参考にしてください。
裏 EDPC・裏 TDPC
EDPC B – Frog 2
2024-02-26 追加
現在位置の足場の高さを $h$ とすると、行先は、
- $1$ 回で行ける高さ $h$ 以上の足場のうち最も低いものと、
- $1$ 回で行ける高さ $h$ 以下の足場のうち最も高いもの
の高々 $2$ 通りに絞ってもよい。これらの行先は平衡二分探索木で取得できるので全体で $O(N\log K)$ 時間。
see also : https://twitter.com/NachiaVivias/status/1761766559683350655
EDPC F – LCS
bit 並列化によるワードサイズ高速化がある。
まず各文字種について $s$ 中にその文字がある位置をビット列に書き込む。
LCS の DP の差分を管理する。差分は $0$ か $1$ の値であるからそのままビット列に入れられる。つまり $\text{dp}[p]=\text{LCS}(s[1\ldots p+1],t[1\ldots q])-\text{LCS}(s[1\ldots p],t[1\ldots q])$ をビット列で管理する。
$t$ の $i$ 文字目を見ているとき、暫定 LCS が $k$ となる変化点が新しく発生する場所は、 $k-1$ となる変化点と $k$ となる変化点の間（境界を含まない）であって、文字 $t_i$ が $s$ 中にある場所のうち最も先に来るものである。これによる配列 $\text{dp}$ の変化は引き算とビット演算で一度に更新できる。
$|s|$ と $|t|$ が $w$ に対して十分に大きいとき $O(|s|(\sigma + |t|)/w)$ 時間。
参考：編集距離を O(NM/w) 時間で求めるアルゴリズム – TechFULの中の人
関連：うにゅーん、って感じだ「LCS を時間 O(|S| |T| / w)、空間 O(|S| + |T|) で復元までやる」 りあん より
関連：rogi52’s blog「LCS のワードサイズ高速化」
EDPC I – Coins
コインを多項式 $(1-p_i)+p_ix$ で表し、総積を FFT を使って高速に計算する。 $O(N(\log N)^2)$ 時間。
EDPC L – Deque
“An Optimal Algorithm for Calculating the Profit in the Coins in a Row Game” によると、 $O(N)$ 時間。(*1)
出題例 (Project Euler) (*2)
(*1) 情報元 https://twitter.com/hotmanww/status/1726986294033784942
(*2) hidesugar(9) より教えていただいた。
EDPC M – Candies
DP による素直な解法は $O(NK)$ 時間。
条件が $a_i=p$ の子供が $n_p$ 人いるとする。（ ${}\bmod (10^9+7)$ を無視すると、）求める値は形式的べき級数を用いて
$$ [x^K]\prod_p \left( \frac{1-x^{p+1}}{1-x} \right)^{n_p} $$
と表せる。変形すると
$$ \prod_p \left( \frac{1-x^{p+1}}{1-x} \right)^{n_p} = \exp\left( -N\log (1-x) + \sum_p n_p \log (1-x^{p+1}) \right) $$
となる。 $\log (1-x^d)$ を明に計算して、 $\exp(f)$ は畳込みから計算することにより、 $O(N + K \log K)$ 時間。
参考： $\# _p$ Subset Sum – Library Checker
maspy さんの投稿 「累積和による dp 遷移の導出」で EDPC M – Candies が参照されている。
EDPC N – Slimes
計算対象と入出力形式までまったく同じで、 $n\leq 10^5$ まで拡大した問題が AtCoder Typical Contest 002 で出題されている。これは実に最適二分探索木問題そのものであり、 Hu–Tucker algorithm により $O(N\log N)$ 時間。
EDPC R – Walk
行列累乗では $O(N^3 \log K)$ 時間。そもそも行列積が高速化するという話もあるが、競プロではほぼ使われない。以下は別のアプローチである。
求める値は行列 $A$ とベクトル $\bm{v},\bm{w}$ を用いて
$$X={}^t\bm{w}A^k\bm{v}$$
と表せる。 $A$ の固有多項式を $f(\lambda)$ とすれば $f(A)=O$ （ケーリー・ハミルトンの定理）なので、 $F(x)= x^K \bmod f(x)$ とすれば
$$X={}^t\bm{w}F(A)\bm{v}=\sum_{n=0}^{N-1}({}^t\bm{w}A^n\bm{v})\cdot [x^n]F(x)$$
と計算できる。特に $A^n\bm{v}$ の列挙は $O(N^3)$ 時間でできる。計算量は $O(N^3 + N\log N\log K)$ 。
実装例 一部改善を省略し、 $O(N^3 + N^2\log N\log K)$ 時間にしている。
2024-01-24 追記分
乱択によって行列累乗を $O(N^3+N\log N\log K)$ 時間で計算できる方法が codeforces blog で紹介された。
EDPC T – Permutation
包除原理で < を消去する。
> と ? からなる長さ $N-1$ の文字列が与えられる。いくつかの ? を > に置き換えたのち、その不等号をすべて満たす順列を数え上げる。ただし、文字を変えた個数を $k$ として寄与を $(-1)^k$ 倍する。総和はいくらか。
> のみで接続される区間内の大小関係は $1$ 通りであり、それらが ? で連結される場合は指数型母関数の要領で計算できる。この数え上げは、 ? を $k$ 個置き換えて形成した > が $n$ 個連続する区間について $\frac{(-1)^k}{(n+1)!}$ 倍で遷移する DP で計算できる。この DP は分割統治畳込み（分割統治 FFT ）で高速化できる。計算量は $O(N(\log N)^2)$ 時間。
実装例 見やすさのため畳込みは愚直に実装してある。
ある他の AtCoder の問題の想定解を参考にした。
TDPC O – 文字列
nok0 さんによるユーザ解説 より。
総文字数を $Z$ 、各文字種の文字数の $2$ 乗の和を $Y$ とおく。典型的な挿入 DP では $O(ZY)$ 時間。高速な方法は $O(Z(\log Z)^2)$ 時間である。
TDPC P – うなぎ
$O(NK)$ の木 DP であり、計算量は $O(NK)$ 時間である。 $K\leq 50$ という制約は実は特段意味をなさない。
参考：木と計算量 前編 〜O(N^2)とO(NK)の木DP〜 – あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
2023-12-23 追記分
また、実際の効率は悪いが、 top tree ( cluster のマージ過程 ) と畳込みを利用して $O(N(\log N)^2)$ 時間の解法を作ることもできる。
TDPC S – マス目
ほとんど同じ設定で $H\leq 9,W\leq 10^{18}$ まで拡大した出題がある。 yukicoder No.1561 connect x connect
(追記)改めて確認したところ、執筆時の私は問題設定を勘違いしてしまっており、実際は TDPC S と yukicoder No.1561 は本質的に異なる計算であることに気づいた。ただしアプローチの本質は変わらない。また、執筆時想定していた方法は connect x connect の解説ページで解説されていなかったため、以下で少し説明する。
走査線をなす $H$ マスの連結関係および左上のマスと連結している連結成分の組を状態として DP を組むと、全体は行列累乗で表せる。答えは EDPC R – Walk でも現れた ${}^t\bm{w}A^n\bm{v}$ 型であり、線形漸化式を持つ。ここで Berlekamp–Massey 法を適用するためには先頭から十分な個数の項を求める必要があるが、 DP の遷移を $1$ マスずつに分けて処理すると、状態数の最大値を $p(H)$ として $O(H(p(H))^2)$ 時間となる。 Bostan–Mori 法で必要な項を求めれば全体の計算量はおおまかに見積もって $O(H(p(H))^2+p(H)\log p(H) \log W)$ である。例えば $H=9$ , $W=10^{18}$ という入力では $p(H)=6010$ ととれて、制限時間に間に合う。
TDPC T – フィボナッチ
線形漸化式をもつ数列の第 $K$ 項の計算である。今では Bostan–Mori 法という割とシンプルなアルゴリズムがよく知られているが、当時「きたまさ法」と呼ばれる $2$ 乗時間かけるアルゴリズムが主流だったときもあったようだ(参考：よすぽの日記)。
参考： 線形漸化的数列のN項目の計算 – ryuhe1(Ryuhei Mori)@Qiita