(正式な解説は後日公開されます)

各問題のテーマをヒント形式で列挙しました。

A 問題

動的計画法で問題を解くときは、何を状態として持てば動的計画法が機能するかを意識することを心がけましょう。

B 問題

メモ化再帰 を利用するとすっきり解くことが出来る問題です。トポロジカル順 を利用する方法もあります。

C 問題

DP 上の DP(仮称) で解くことが出来ます。

• この種の DP は 耳 DP と呼ぶ人もいますが何を指しているかわかりづらく好みの呼び方でないため中国における呼称を元に命名しました。他の命名候補として オートマトン DP なども考えられそうです。

D 問題

一見 \(\mathrm{O}(N)\) 時間かかりそうですが、遷移を工夫すると状態数を削減することが出来ます。

E 問題

ダブリング を利用するとすっきり解くことが出来ます。

F 問題

列のまま問題を解くことは難しそうです。Cartesian Tree を構築することで 2 乗の木 DP を行うことが出来ます。

G 問題

部分点は 耳 DP の命名の由来となった Ears という問題と全く同じ DP で解くことが出来ます。
また、この種の DP はセグメント木に載せることで 動的な DP の更新 が可能となります。

H 問題

bool を値に持つ DP で \(\mathrm{O}(N^3)\) になりますが TLE してしまいます。
「bool 値 DP は無駄が多いので次元落としを考える」という典型があります。

I 問題

挿入 DP と呼ばれる DP で解くことが出来ます。

J 問題

繰り上がりを持つ桁 DP で解くことが出来ます。繰り上がりを持つ桁 DP の解説は ABC300 Ex 解説の冒頭 に詳しいです。

K 問題

適切な言い換えを行うことで 部分和問題 に帰着されます。

L 問題

約数ゼータ変換の発想を応用すると解くことが出来ます。AGC や ARC でしばしば出題されるテクニックです。問題例 1, 問題例 2

M 問題

高速ゼータ変換 (別名 SOS DP, Subset Of Sum DP の略) を利用すると解くことが出来ます。

N 問題

ナップサック問題の 1 種で、個数制限がないことから専門的には unbounded knapsack problem と呼ばれる問題です。
この問題は \(\mathrm{O}(N^3)\) で解く解法がよく知られていますが、実は少し工夫すると計算量を \(\mathrm{O}(N^2 \log N)\) に落とすことが出来ます。

O 問題

部分点

考察を要求する問題です。偶奇性に注目して議論を進めることで上手く max-plus 畳み込み に帰着しましょう。

満点

方針は色々ありますが、想定解は Alien DP を用いています。

P 問題

名前はついていない DP ですが、面白くないビットすごろく DP と言えば通じる人には通じる DP かもしれません。
いずれにせよ DP の遷移を詰め切る力を要求する問題です。何を状態に持てば DP できるかを考察しましょう。

Q 問題

自然に DP を行うと空間計算量が \(\mathrm{O}(NM)\) になり困ってしまいます。想定解では 多項式補間 の考えを利用して空間計算量を改善しています。

R 問題

部分点・満点ともに様々な解法があります。 毒蛇の脱走 や ARC205 E が類題です。

S 問題

この問題は適切に議論を行うと「頂点 \(A, B\) を通る \(S-T\) 最短パス」を計算する問題に帰着されます。ここで求めるものがパスである点がポイントで、自然なダイクストラ法ではウォークを除去できず失敗します。
複数の特定の頂点を通る最短パスを求める問題は 標数 2 の体 を用いた特殊な DP を行うことで計算できます。

T 問題

部分点

static top tree の練習問題です。
static top tree に関しては ABC351 G 公式解説 が非常によくまとまっているのでこちらを参照してください。

満点

static top tree 上でかなり高度な DP を行います。
発想難度が高く、またそれ以上に実装が大変な問題だと思います。ぜひ挑戦してみてください。