裏 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 B – Frog 2

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

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 の問題の想定解を参考にした。

TDPC P – うなぎ

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 – マス目

S – マス目

ほとんど同じ設定で $H\leq 9,W\leq 10^{18}$ まで拡大した出題がある。 yukicoder No.1561 connect x connect

TDPC T – フィボナッチ

T – フィボナッチ

線形漸化式をもつ数列の第 $K$ 項の計算である。今では Bostan–Mori 法という割とシンプルなアルゴリズムがよく知られているが、当時「きさまた法」と呼ばれる $2$ 乗時間かけるアルゴリズムが主流だったときもあったようだ(参考:よすぽの日記)。

参考: 線形漸化的数列のN項目の計算 – ryuhe1(Ryuhei Mori)@Qiita

関連

典型 $90$ 変形集 – noshi91

タイトルとURLをコピーしました