Educational DP Contest

EDPC を全部埋めた。雑多なメモなので、きれいに解法をまとめたものではない。

W - intervals

$dp_i$ を、いくつかのビットに1が立っているとき、最も右側にある1が$i$であるときの最終スコアとする。ここで、$dp_i$は$ max_{j=0 … i-1} dp_j$ と $i$ 文字目を1にしたときに得られるスコアの和で求められる。 $block_i$を右端$r$が$i$であるブロックの集合として、 $dp_i$を計算する際に、 $i$文字目を1にしたときに得られるスコアとして $block_i$ を足しこむ。 $block_i$ は $i$ 未満の $dp$ にも影響するため、遅延セグメントツリーを使って、影響する $dp$ に区間加算を行う。最終的な答えは $max_{i=0 … N} dp_i$ となる。はじめて、遅延セグメントツリーを使った。復習しておく。

Z - Frog 3

$dp_i$ を足場 $i$ に到達するまでの最小コストする。初期値は $dp_0 = 0$。まずは素直にDPの更新式を作ると以下のようになる。

$$ \begin{aligned} dp_i &= min_{j=0 … i-1} (dp_j + (h_j - h_i)^2 + C) \\ &= min_{j=0 … i-1} (dp_j + h_j^2 - 2 h_i h_j + h_i^2 + C) \\ &= min_{j=0 … i-1} (-2 h_i h_j + dp_j + h_j^2) + h_i^2 + C \\ \end{aligned} $$

ここで、$f_j(x) = -2 h_j x + dp_j + h_j^2$ とすると、$f_j$は一次式として表すことができ、 Convex Hull Tree によって最小値を計算することができる。今回は、$x$の範囲が限られているので Li Chao Tree を使った。ちなみに、$dp_i$ を $f_j$ を使って置き換えると以下のようになる。

$$ dp_i = min_{j=0 … i-1} f_j(h_i) + h_i^2 + C $$

ナイーブなDP更新式を考えることはできたが、そこから Convex Hull Tree へ繋げられなかった。

Y - Grid 2

$dp_i$ を $0 … i-1$ のブロックにぶつかることなく、ブロック $i$ に到達するパターン数とする。なお、あらかじめゴール地点をブロックとして追加しておくと、答えは $dp_N$ となる（0-indexed）。また、$route(i)$ をスタート地点からブロック$i$への遷移のパターン数、 $route(j,i)$ をブロック$j$からブロック$i$への遷移のパターン数とする。これらは、ブロックの衝突は考慮しないので、事前に求めておく。 DPの更新式は以下の通り。

$$ \begin{aligned} dp_0 &= route(0) \\ dp_i &= route(i) - \sum_{j=0}^{i-1} dp_j \cdot route(j,i) \end{aligned} $$

X - Tower

ブロックを上の段から貪欲においていくことにする。そこで、あらかじめ何らかの順番にブロック達を並び替えておく必要がある。ブロック$i$ とブロック$j$があって、どちらを先に（上に）おいた方がよいかを考える。ブロック$i$を上段、ブロック$j$を下段に配置したときは、それらのブロックの上における重さは、 $min(s_i, s_j-w_i)$ となる。同様に逆順にすれば、$min(s_j, s_i-w_j)$となる。つまり、ブロック$i$を先においたほうが良いのは、$min(s_i, s_j - w_i) > min(s_j, s_i - w_j)$ の場合。これを展開して $s_i + w_i < s_j + w_j$を満たすときに $i$ を $j$ より優先させて上に置いていけばよい。

V - Subtree

全方位木DP。まず、頂点0を根とする木を考えたとき、頂点$i$以下の部分木が条件を満たす組み合わせ数を$dp_i$とする。更新式は、以下の通り。

$$ dp_i = \prod_{c \ \in \ children \ of \ i} (dp_c + 1) $$

この$dp$をもとに、各頂点ごとに全方位木DPを行う。割り算が使えないので、全方位木DPを行う際に、prefixとsuffixを事前計算して、特定の頂点に対する値だけを計算対象から外すといったテクニックが必要になる。

T - Permutation

$dp_{i,j}$を$i$番目までの値を決めたとき、$i$番目の値が残りの集合の中で、$j$番目に小さい時の組み合わせ数とする。初期値は以下の通り。

$$ \begin{aligned} dp_{0,0} &= 1 \\ dp_{0,1} &= 1 \\ \vdots \\ dp_{0,N-1} &= 1 \\ \end{aligned} $$

今回は配るDPでやっていく。まず、$s_i$が>の場合は、$0 … j-1$の数を選ぶことができる。

$$ \begin{aligned} dp_{i+1,0} &+= dp_{i,j} \\ dp_{i+1,1} &+= dp_{i,j} \\ \vdots \\ dp_{i+1,j-1} &+= dp_{i,j} \\ \end{aligned} $$

続いて、$s_i$が < の場合、$j+1 … N-i-1$の数を選ぶことができる。

$$ \begin{aligned} dp_{i+1,j} &+= dp_{i,j} \\ dp_{i+1,j+1} &+= dp_{i,j} \\ \vdots \\ dp_{i+1,N-i-2} &+= dp_{i,j} \\ \end{aligned} $$

U - Grouping

$S$をウサギの集合をビットマップで持ったものとする。ウサギは最大16羽しかいないので計算は間に合う。 $dp_S$は、集合$S$のうさぎをグループ分けしたときのスコアの最大値とする。なお、$sum(S)$は$S$を1つのグループとしたときのスコア。

$$ \begin{aligned} dp_{\phi} &= 0 \\ dp_{S} &= max_{U \subset S} (dp_U + sum(S-U)) \\ \end{aligned} $$

ここで、部分集合の列挙は工夫する必要がある。単純に列挙すると$O(2^N \cdot 2^N)$ かかるが、工夫すると $O(3^N)$で抑えられる。

for (S = 1; S < (1 << N); S++) {
  for (U = (S-1) & S; ; U = (U-1) & S) {
    // DP更新処理
    ...
    if (U == 0)
      break;
  }
}

R - Walk

$dp_{k,i,j}$ を長さ$2^k$で頂点$i$から頂点$j$へ移動するパスのパターン数とする。

$$ \begin{aligned} dp_{0,i,j} &= a_{i,j} \\ dp_{k,i,j} &= \sum_{u=0}^{N-1} dp_{k-1,i,u} \cdot dp_{k-1,u,j} \\ \end{aligned} $$

S - Digit Sum

$K$の上位の桁から順に$0,1, …, N-1$とインデックスを割り振る。 $dp_{i,j,s}$ を、上から$i$桁目まで見たときに、あまりが$s$であるパターン数とする。なお、$i$桁目までが$K$と完全に一致している場合には$j=1$とする。配るDPでやっていく。まず、初期値は以下の通り。

$$ \begin{aligned} dp_{0,0,0} &= 1 \\ \vdots \\ dp_{0,0,(k_0 - 1) \bmod D} &= 1 \\ dp_{0,1,k_0 \bmod D} &= 1 \\ \end{aligned} $$

更新式は、$dp_{i,0,s}$と$dp_{i,1,s}$のどちらから配るかによって異なる。

$$ \begin{aligned} dp_{i+1,0,(s+0) \bmod D} &+= dp_{i,0,s} \\ \vdots \\ dp_{i+1,0,(s+9) \bmod D} &+= dp_{i,0,s} \\ \end{aligned} $$

$$ \begin{aligned} dp_{i+1,0,(s+0) \bmod D} &+= dp_{i,1,s} \\ \vdots \\ dp_{i+1,0,(s+k_{i+1}-1) \bmod D} &+= dp_{i,1,s} \\ dp_{i+1,1,(s+k{i+1}) \bmod D} &+= dp_{i,1,s} \\ \end{aligned} $$