裏 EDPC・裏 TDPC

EDPC と TDPC の出題のうち、題意よりも強いか効率的な解法があるもの。

Educational DP Contest : (https://atcoder.jp/contests/dp)

Typical DP Contest : (https://atcoder.jp/contests/tdpc)

説明は詳細ではない。実装例および外部の出題を参考にしてください。

changelog

2024-02-22 実装例中の無駄な実装を削減しました。

2024-02-26 EDPC B – Frog 2 を追加しました。

裏 EDPC・裏 TDPC
関連

裏 EDPC・裏 TDPC

EDPC B – Frog 2

B – Frog 2

2024-02-26 追加

現在位置の足場の高さを $h$ とすると、行先は、

$1$ 回で行ける高さ $h$ 以上の足場のうち最も低いものと、
$1$ 回で行ける高さ $h$ 以下の足場のうち最も高いもの

の高々 $2$ 通りに絞ってもよい。これらの行先は平衡二分探索木で取得できるので全体で $O(N\log K)$ 時間。

実装例

EDPC F – LCS

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の中の人

実装例

EDPC I – Coins

I – Coins

コインを多項式 $(1-p_i)+p_ix$ で表し、総積を FFT を使って高速に計算する。 $O(N(\log N)^2)$ 時間。

実装例

EDPC L – Deque

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

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

実装例

EDPC N – Slimes

N – Slimes

計算対象と入出力形式までまったく同じで、 $n\leq 10^5$ まで拡大した問題が AtCoder Typical Contest 002 で出題されている。これは実に最適二分探索木問題そのものであり、 Hu–Tucker algorithm により $O(N\log N)$ 時間。

EDPC R – Walk

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

T – Permutation

包除原理で < を消去する。

> と ? からなる長さ $N-1$ の文字列が与えられる。いくつかの ? を > に置き換えたのち、その不等号をすべて満たす順列を数え上げる。ただし、文字を変えた個数を $k$ として寄与を $(-1)^k$ 倍する。総和はいくらか。

> のみで接続される区間内の大小関係は $1$ 通りであり、それらが ? で連結される場合は指数型母関数の要領で計算できる。この数え上げは、 ? を $k$ 個置き換えて形成した > が $n$ 個連続する区間について $\frac{(-1)^k}{(n+1)!}$ 倍で遷移する DP で計算できる。この DP は分割統治畳込み（分割統治 FFT ）で高速化できる。計算量は $O(N(\log N)^2)$ 時間。

実装例見やすさのため畳込みは愚直に実装してある。

ある他の AtCoder の問題の想定解を参考にした。