【AtCoder】「分野別　初中級者が解くべき過去問精選 100 問」解答例【動的計画法：ナップザック DP】(2/3)

この記事は【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみたの子記事です。お読みになる前に親記事をご確認ください。

41. JOI 2013 予選 4 – 暑い日々

問題へのリンク

$D$ 日間の服の計画をすべて列挙して派手さの差の絶対値の合計を計算する場合、計算量は $\Omega(D N^D)$ となり、制限時間を超えそうです。

値 $|C_{x_1} − C_{x_2}| + |C_{x_2} − C_{x_3}| + \cdots + | C_{x_{D − 1}} − C_{x_D}|$ の最大値を動的計画法の更新式に変形できないか考えます。

$\begin{aligned} \max_{\{x_i\}_{i=1}^D} \sum_{i = 1}^{D-1} | C_{x_i} – C_{x_{i+1}} | =& \max_{x_D} \max_{\{x_i\}_{i=1}^{D-1}} \sum_{i = 1}^{D-1} | C_{x_i} – C_{x_{i+1}} | \\ \max_{\{x_i\}_{i=1}^{D-1}} \sum_{i = 1}^{D-1} | C_{x_i} – C_{x_{i+1}} | =& \max_{x_{D-1}} \max_{\{x_i\}_{i=1}^{D-2}} \left ( \sum_{i = 1}^{D-2} | C_{x_i} – C_{x_{i+1}} | + | C_{x_{D – 1}} – C_{x_D} | \right ) \\ =& \max_{x_{D-1}} \left ( \max_{\{x_i\}_{i=1}^{D-2}} \sum_{i = 1}^{D-2} | C_{x_i} – C_{x_{i+1}} | + | C_{x_{D – 1}} – C_{x_D} | \right ) \end{aligned}$

上記の式変形から $\mathrm{dp}[i][j]$ を $i$ 日目に服 $j$ を着る $i$ 日目までの服の計画の集合の派手さの差の絶対値の最大値とすると、以下の更新式が成り立ちます。

$\mathrm{dp}[i + 1][j] = \max_{k} (\mathrm{dp}[i][k] + |C_{k} – C_{j}|)$

天気予報に従って着るのに適した服を選ぶため、以下のように更新式を修正します。

$\mathrm{dp}[i + 1][j] = \begin{cases} -1&(T_{i + 1}<A_j \,\text{または} \, B_j<T_{i + 1}) \\ \max_{k, \mathrm{dp}[i][k] \geq 0} (\mathrm{dp}[i][k] + |C_{k} – C_{j}|)&(A_j \leq T_{i+1} \leq B_j) \end{cases}$

問題文に以下の記述があるため、任意の $i$ に対し $\mathrm{dp}[i][k] \geq 0$ となる $k$ が存在することに注意します。

最高気温が天気予報に従ったときに着るのに適した服が， $D$ 日間のどの日に対しても $1$ つ以上存在することが保証されている．

$\mathrm{dp}[1][j]$ は以下のように着るのに適した服については $0$ , 適さない服については $-1$ とします。

$\mathrm{dp}[1][j] = \begin{cases} -1&(T_{1}<A_j \,\text{または} \, B_j<T_{1}) \\ 0&(A_j \leq T_{1} \leq B_j) \\ \end{cases}$

$\max_{j} \mathrm{dp}[D][j]$ が求める最大値です。

$\mathrm{dp}[i][j]$ の一度の更新に $O(N)$ かかるため、全体の計算量は $O(DN^2) = 10^7$ 程度です。

解答例 1

JOI の解説に以下の記述があります。

なお，この問題に対しては，より効率の良い方法が存在する．実は，各日の服の候補のうち， $C_j$ が最大のものまたは最小のものの 2 通りのみを考えればよいことが証明できる．

上記を考えてみます。

主張を数式で記述します。 $C^i_{\max}$ , $C^i_{\min}$ を $i$ 日の服の候補の派手さの最大値, 最小値とします。上記は以下のように表現できます。

$\max_{\{x_i\}_{i=1}^{D}} \sum_{i = 1}^{D-1} | C_{x_i} – C_{x_{i+1}} | = \max_{C_{x_i} \in \{C^i_{\min}, C^i_{\max} \}} \sum_{i = 1}^{D-1} | C_{x_i} – C_{x_{i+1}} |$

$f^d (y)$ を以下のように定義します。

$f^d (y) \coloneqq \max_{\{x_i\}_{i=1}^{d-1}} \left(\sum_{i = 1}^{d-2} |C_{x_i} – C_{x_{i+1}}| + |C_{x_{d-1}} – y |\right)$

元の主張は以下の 2 つの等式が成立するならば示すことができます。

$f^d (y) = \max_{C_{x_i} \in \{C^i_{\min}, C^i_{\max} \}} \left(\sum_{i = 1}^{d-2} |C_{x_i} – C_{x_{i+1}}| + |C_{x_{d-1}} – y |\right)$

$\max_{x_d, A_{x_d} \leq T_d \leq B_{x_d}} f^d (C_{x_d}) = \max_{C_{x_d} \in \{C^i_{\min}, C^i_{\max} \}} f^d (C_{x_d})$

$1$ つめの等式を $d$ についての数学的帰納法で示します。

step 1 　 $d = 2$ のとき

${\tilde{x}}_{1}$ を $\max_{x_1} |C_{x_1} – y| = |C_{\tilde{x}_1} – y|$ を満たす服とします。 $C_{\tilde{x}_1} \leq y$ のとき、以下の式変形から $1$ つめの等式は成立します。

$\max_{x_1} |C_{x_1} – y| = |C_{\tilde{x}_1} – y| = y – C_{\tilde{x}_1} \leq y – C^1_{\min} \leq \max_{C_{x_1} \in \{C^1_{\min}, C^1_{\max} \}} | C_{x_1} – y |$

$C_{\tilde{x}_{1}}>y$ のときは $C_{\tilde{x}_1} – y \leq C^1_{\max} – y$ を用いて同様に示すことができます。

step 2 　 $d \leq d_0$ では成立すると仮定したとき

$\{{\tilde{x}}_i\}_{i=1}^{d_0}$ を以下が成立する服の組み合わせとします。

$f^{d_0 + 1} (y) = \sum_{i=1}^{d_0 – 1} |C_{\tilde{x}_i} – C_{\tilde{x}_{i+1}}| + |C_{\tilde{x}_{d_0}} – y|$

次のように式変形します。

$f^{d_0 + 1} (y) = \sum_{i=1}^{d_0 – 2} |C_{\tilde{x}_i} – C_{\tilde{x}_{i+1}}| + |C_{\tilde{x}_{d_0 – 1}} – C_{\tilde{x}_{d_0}}| + |C_{\tilde{x}_{d_0}} – y|$

第 $1$ 項は帰納法の仮定を使って処理することを想定し、第 $2$ 項と第 $3$ 項に着目します。
$C_{\dot{x}_{d_0}} \in \{C^{d_0}_{\min}, C^{d_0}_{\max}\}$ を以下のように定義します。

$C_{\dot{x}_{d_0}} = \begin{cases} C^{d_0}_{\min}&(C_{\tilde{x}_{d_0}}<\max(C_{\tilde{x}_{d_0 – 1}}, y)) \\ C^{d_0}_{\max}&(C_{\tilde{x}_{d_0}} \geq \max(C_{\tilde{x}_{d_0 – 1}}, y)) \\ \end{cases}$

$C_{\tilde{x}_{d_0 – 1}}$ , $C_{\tilde{x}_{d_0}}$ , $y$ の大小関係について場合を分けて確認すると以下が成立することがわかります。

$|C_{\tilde{x}_{d_0 – 1}} – C_{\tilde{x}_{d_0}}| + |C_{\tilde{x}_{d_0}} – y| \leq |C_{\tilde{x}_{d_0 – 1}} – C_{\dot{x}_{d_0}}| + |C_{\dot{x}_{d_0}} – y|$

この不等式を使って $f^{d_0 + 1} (y)$ を上から評価します。

$\begin{aligned} f^{d_0 + 1} (y) &= \sum_{i=1}^{d_0 – 2} |C_{\tilde{x}_i} – C_{\tilde{x}_{i+1}}| + |C_{\tilde{x}_{d_0 – 1}} – C_{\tilde{x}_{d_0}}| + |C_{\tilde{x}_{d_0}} – y| \\ &\leq \sum_{i=1}^{d_0 – 2} |C_{\tilde{x}_i} – C_{\tilde{x}_{i+1}}| + |C_{\tilde{x}_{d_0 – 1}} – C_{\dot{x}_{d_0}}| + |C_{\dot{x}_{d_0}} – y| \\ &\leq f^{d_0} (C_{\dot{x}_{d_0}}) + |C_{\dot{x}_{d_0}} – y| \end{aligned}$

帰納法の仮定から $f^{d_0} (C_{\dot{x}_{d_0}}) = \sum_{i=1}^{d_0 – 2} |C_{\dot{x}_i} – C_{\dot{x}_{i+1}}| + |C_{\dot{x}_{d_0 – 1}} – C_{\dot{x}_{d_0}}|$ が成立する服の組み合わせ $\{\dot{x}_i\}_{i=1}^{d_0 – 1}$ ( $C_{\dot{x}_i} \in \{C^{i}_{\min}, C^{i}_{\max}\}$ )が存在します。 $\{\dot{x}_i\}_{i=1}^{d_0 – 1}$ を使って $f^{d_0 + 1} (y)$ を上から評価します。

$\begin{aligned} f^{d_0 + 1} (y) &\leq f^{d_0} (C_{\dot{x}_{d_0}}) + |C_{\dot{x}_{d_0}} – y| \\ &= \sum_{i=1}^{d_0 – 2} |C_{\dot{x}_i} – C_{\dot{x}_{i+1}}| + |C_{\dot{x}_{d_0 – 1}} – C_{\dot{x}_{d_0}}| + |C_{\dot{x}_{d_0}} – y| \\ &\leq \max_{C_{x_i} \in \{C^i_{\min}, C^i_{\max} \}} \left(\sum_{i = 1}^{d_0-1} |C_{x_i} – C_{x_{i+1}}| + |C_{x_{d_0}} – y |\right) \end{aligned}$

よって $d = d_0 + 1$ のときも $1$ つめの等式は成立します。

$2$ つめの等式を示します。
$\max_{x_d, A_{x_d} \leq T_d \leq B_{x_d}} f^d (C_{x_d}) = f^d(C_{\tilde{x}_d})$ を満たす $\tilde{x}_{d}$ と $f^d(C_{\tilde{x}_d}) = \sum_{i=1}^{d – 1} |C_{\tilde{x}_i} – C_{\tilde{x}_{i+1}}| + |C_{\tilde{x}_{d – 1}} – C_{\tilde{x}_{d}}|$ を満たす ${\{\tilde{x}_i\}_{i=1}^{d-1}}$ に対し、 $C_{\dot{x}_{d}} \in \{C^d_{\min}, C^d_{\max} \}$ を次のように決めます。

$C_{\dot{x}_{d}} = \begin{cases} C^{d}_{\min}&(C_{\tilde{x}_{d}}<C_{\tilde{x}_{d – 1}}) \\ C^{d}_{\max}&(C_{\tilde{x}_{d}} \geq C_{\tilde{x}_{d – 1}}) \\ \end{cases}$

$|C_{\tilde{x}_{d – 1}} – C_{\tilde{x}_{d}}| \leq |C_{\tilde{x}_{d – 1}} – C_{\dot{x}_{d}}|$ が成立するため、以下の不等式が成立し、2 つめの等式が成立します。

$\max_{x_d, A_{x_d} \leq T_d \leq B_{x_d}} f^d (C_{x_d}) = f^d(C_{\tilde{x}_d}) \leq f^d(C_{\dot{x}_d}) \leq \max_{C_{x_d} \in \{C^i_{\min}, C^i_{\max} \}} f^d (C_{x_d})$

以上から下記の式変形ができ、元の主張が示せます。

$\begin{aligned} \max_{\{x_i\}_{i=1}^{D}} \sum_{i = 1}^{D-1} | C_{x_i} – C_{x_{i+1}} | &= \max_{x_D, A_{x_D} \leq T_D \leq B_{x_D}} f^D (C_{x_D}) = \max_{C_{x_D} \in \{C^D_{\min}, C^D_{\max} \}} f^D (C_{x_D}) \\ &= \max_{C_{x_D} \in \{C^D_{\min}, C^D_{\max} \}} \max_{C_{x_i} \in \{C^i_{\min}, C^i_{\max} \}} \left(\sum_{i = 1}^{d-2} |C_{x_i} – C_{x_{i+1}}| + |C_{x_{d-1}} – c_{x_d}|\right) \\ &= \max_{C_{x_i} \in \{C^i_{\min}, C^i_{\max} \}} \sum_{i = 1}^{D-1} | C_{x_i} – C_{x_{i+1}}| \end{aligned}$

よって、動的計画法を行う際、各日の服の候補のうち， $C_j$ が最大のものまたは最小のものの $2$ 通りのみ更新すれば良いことがわかりました。 $\mathrm{dp}[i][j]$ を以下のように定義しなおします。

$\mathrm{dp}[i][0]$ を以下を満たす $i$ 日目までの服の計画の派手さの差の絶対値の最大値とします。

第 $i$ 日目に気温 $T_i$ に適した服の候補の中で派手さが最小の服を着る。

$\mathrm{dp}[i][1]$ を以下を満たす $i$ 日目までの服の計画の派手さの差の絶対値の最大値とします。

第 $i$ 日目に気温 $T_i$ に適した服の候補の中で派手さが最大の服を着る。

$\mathrm{dp}[i][j]$ の更新式は以下のようになります。

$\begin{aligned} \mathrm{dp}[i + 1][0] &= \max (\mathrm{dp}[i][0] + |C^{i}_{\min} – C^{i + 1}_{\min}|, \mathrm{dp}[i][1] + |C^{i}_{\max} – C^{i + 1}_{\min}|) \\ \mathrm{dp}[i + 1][1] &= \max (\mathrm{dp}[i][0] + |C^{i}_{\min} – C^{i + 1}_{\max}|, \mathrm{dp}[i][1] + |C^{i}_{\max} – C^{i + 1}_{\max}|) \\ \end{aligned}$

$\mathrm{dp}[1][j]$ についてはすべて $0$ とします。 $\mathrm{dp}[i][0], \mathrm{dp}[i][1]$ の更新のたびに $C^i_{\min}, C^i_{\max}$ を求める場合、一度の更新の計算量は $O(N)$ になります。全体の計算量は $O(DN) = 10^5$ 程度です。

解答例 2

注意以下ではレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】の「2-1. 「水色コーダー」で要求される 4 つのこと」の「条件 2」には記載のないデータ構造「遅延評価セグメント木」を用います。

解答例 2 では $C^i_{\min}, C^i_{\max}$ を $\mathrm{dp}[i][j]$ の更新のたびに計算量 $O(N)$ で算出しました。遅延評価セグメント木を用いると以下の計算量で $C^i_{\min}, C^i_{\max}$ を求められます。

前処理 $O(N \log (\max_{j} B_j))$
クエリ $O(\log(\max_{j} B_j))$

遅延評価セグメント木についてレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【上級編：目指せレッドコーダー！】では遅延評価セグメント木をソラで書きたいあなたにが紹介されています。AtCoder Library Practice Contest には以下のセグメント木や遅延評価セグメント木の典型問題があります。

私の感覚しか根拠はありませんが、問題 K, L は本問題での遅延評価セグメント木の応用よりも難しいです。そのため、セグメント木や遅延評価セグメント木に不慣れな方は以下の手順で読み進めていただけばと存じます。

この問題では以下のように遅延評価セグメント木の使います。

気温 $T$ ( $0 \leq T \leq \max_{j} B_j$ ) を添字とする服の派手さの遅延評価セグメント木を最小値用と最大値用の 2 つ用意します。
服 $j$ ごとに各遅延評価セグメント木の範囲 $[A_j, B_j]$ を $C_j$ で更新します。
各 $i$ について各遅延評価セグメント木から添字 $T_i$ の値を取得し、 $\mathrm{dp}[i][j]$ を更新します。

遅延評価セグメント木の実装は AtCoder Library の lazysegtree を使います。lazysegtree を使うために以下を準備します。

モノイド $(S, \cdot)$
モノイド $S$ 上の半群準同型写像全体 $\mathrm{Hom} (S, S)$ の部分モノイド $F$

最大値用の遅延評価セグメント木の上記を $(S_{\max}, \cdot), F_{\max}$ と書くことにします。
$(S_{\max}, \cdot)$ は以下のように定義します。

$\begin{aligned} S_{\max}&\coloneqq \left \{n \in \mathbb{N} \Big | 0 \leq n \leq \max_j C_j \right \} \\ \cdot &: S \times S \to S ; (a, b) \mapsto \max(a, b) \end{aligned}$

証明は省略しますが、 $(S_{\max}, \cdot)$ は $0$ を単位元とするモノイドになります。

$F_{\max}$ は以下のように定義すると写像の合成を二項演算としたモノイドになります。

$F_{\max} \coloneqq \left \{ f_a: S_{\max} \to S_{\max}; x \mapsto a \cdot x = \max(a, x) | a \in S_{\max} \right \}$

$S_{\max}$ と $F_{\max}$ は $a \mapsto f_a$ を同型写像として同型になります。
単射性のみ示します。 $f_a = f_b$ とすると以下の計算から $a = b$ が示されます。

$\begin{aligned} a = \max(a, a) &= f_a (a) = f_b (a) = \max(b, a) = \max(a, b) = f_a (b) = f_b (b) = \max(b, b) = b \end{aligned}$

$F_{\max}$ が $\mathrm{Hom} (S_{\max}, S_{\max})$ の部分モノイドであることを確認します。
$a, x, y \in S_{\max}$ とします。

$\begin{aligned} f_a(x \cdot y) &= a \cdot (x \cdot y) = \max(a, \max(x, y)) = \max(\max(a, x), \max(a, y)) \\ &= (a \cdot x) \cdot (a \cdot y) = f_a (x) \cdot f_a(y) \end{aligned}$

よって、任意の $a \in S_{\max}$ に対し $f_a \in \mathrm{Hom} (S_{\max}, S_{\max})$ となり $F_{\max} \subseteq \mathrm{Hom} (S_{\max}, S_{\max})$ が成立します。
特に $f_0$ が恒等写像であるため、 $\mathrm{Hom} (S_{\max}, S_{\max})$ の単位元である恒等写像は $F_{\max}$ に属します。
$F_{\max}$ は写像の合成 (二項演算) に対し閉じているため、 $\mathrm{Hom} (S_{\max}, S_{\max})$ の部分モノイドになります。

$(S_{\min}, \cdot)$ , $F_{\min}$ も同様に定義します。注意としては $(S_{\min}, \cdot)$ の単位元は $\max_j C_j$ になります。( $C_j \leq 100$ であるため、実装では $100$ として良いです)

lazysegtree のドキュメントによると lazysegtree を使うためには以下を実装する必要があります。

モノイド $S$ の型 S
二項演算 $\cdot : S \times S \to S$ を計算する関数 S op(S a, S b)
モノイド $S$ の単位元 $e$ を返す関数 S e()
写像の集合の型 F
値 $f(x)$ を返す関数 S mapping(F f, S x)
写像 $f \circ g$ を返す関数 F composition(F f, F g)
恒等写像 $\mathrm{id}$ を返す関数 F id()

ただ、この問題の場合は $S_{\max} \simeq F_{\max}$ , $S_{\min} \simeq F_{\min}$ であり、 $S_{\max}$ , $S_{\min}$ は整数の部分集合なので S, F は int にできます。また、 S op(S a, S b) と S e() を以下のように実装の上、S mapping(F f, S x) と F composition(F f, F g) は S op(S a, S b) を、F id() は S e() を使いまわせます。

// 最小値用
int op_min(int a, int b) {return min(a, b);}
int e_min() {return 100;}
// 最大値用
int op_max(int a, int b) {return max(a, b);}
int e_max() {return 0;}

これらの関数を使って lazysegtree のインスタンスを作成します。

// max_B は B_j の最大値
lazy_segtree<int, op_min, e_min, int, op_min, op_min, e_min> seg_min(max_B + 1);
lazy_segtree<int, op_max, e_max, int, op_max, op_max, e_max> seg_max(max_B + 1);

前処理はメンバ関数 apply を使って各 $j$ について温度の範囲 $[A_j, B_j]$ を $C_j$ で更新します。このとき $C_j$ と $f_{C_j} : x \mapsto C_j \cdot x$ を同一視していることにご注意ください。

$\mathrm{dp}[i][j]$ の更新時はメンバ関数 get で気温が $T_i$ のときの適した服の候補の派手さの最小値と最大値をそれぞれの遅延評価セグメント木から取り出します。

前処理に $O(N \log (\max_{j} B_j))$ かかり、 $\mathrm{dp}[i][j]$ の一度の更新に $O(\log (\max_j B_j))$ かかるため、全体の計算量は $O((D + N) \log (\max_j B_j)) = 10^4$ 程度です。

解答例 3