I completed all problems in EDPC. This is a miscellaneous memo, not a cleanly organized solution guide.
W - intervals
Let $dp_i$ be the final score when some bits are set to 1 and the rightmost 1 is at position $i$. Here, $dp_i$ can be calculated as the sum of $ max_{j=0 … i-1} dp_j$ and the score obtained when setting the $i$-th character to 1. Let $block_i$ be the set of blocks whose right end $r$ is $i$. When calculating $dp_i$, add $block_i$ as the score obtained when setting the $i$-th character to 1. Since $block_i$ affects $dp$ values less than $i$, we use a lazy segment tree to perform range addition on the affected $dp$ values. The final answer is $max_{i=0 … N} dp_i$. This was my first time using a lazy segment tree. I’ll review it.
Z - Frog 3
Let $dp_i$ be the minimum cost to reach foothold $i$. Initial value is $dp_0 = 0$. First, writing the DP update formula straightforwardly gives:
$$ \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} $$
Here, letting $f_j(x) = -2 h_j x + dp_j + h_j^2$, $f_j$ can be represented as a linear function, and the minimum value can be computed by a Convex Hull Tree. This time, since the range of $x$ is limited, I used Li Chao Tree. By the way, replacing $dp_i$ with $f_j$ gives:
$$ dp_i = min_{j=0 … i-1} f_j(h_i) + h_i^2 + C $$
I could come up with the naive DP update formula, but couldn’t connect it to the Convex Hull Tree.
Y - Grid 2
Let $dp_i$ be the number of patterns to reach block $i$ without hitting blocks $0 … i-1$. Note that by adding the goal position as a block in advance, the answer becomes $dp_N$ (0-indexed). Also, let $route(i)$ be the number of transition patterns from the start point to block $i$, and $route(j,i)$ be the number of transition patterns from block $j$ to block $i$. These can be calculated in advance since block collisions are not considered. The DP update formula is as follows:
$$ \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
We decide to place blocks greedily from the top layer. Therefore, we need to sort the blocks in some order in advance. Consider which of block $i$ and block $j$ should be placed first (on top). When block $i$ is placed in the upper layer and block $j$ in the lower layer, the weight that can be placed on top of these blocks is $min(s_i, s_j-w_i)$. Similarly, in reverse order, it becomes $min(s_j, s_i-w_j)$. That is, it’s better to place block $i$ first when $min(s_i, s_j - w_i) > min(s_j, s_i - w_j)$. Expanding this, we should prioritize placing $i$ above $j$ when $s_i + w_i < s_j + w_j$ is satisfied.
V - Subtree
All-direction tree DP. First, when considering a tree rooted at vertex 0, let $dp_i$ be the number of combinations where the subtree below vertex $i$ satisfies the condition. The update formula is as follows:
$$ dp_i = \prod_{c \ \in \ children \ of \ i} (dp_c + 1) $$
Based on this $dp$, we perform all-direction tree DP for each vertex. Since division cannot be used, when performing all-direction tree DP, we need a technique of pre-calculating prefix and suffix to exclude only the value for a specific vertex from the calculation.
T - Permutation
Let $dp_{i,j}$ be the number of combinations when the value up to the $i$-th position is decided and the $i$-th value is the $j$-th smallest in the remaining set. Initial values are as follows:
$$ \begin{aligned} dp_{0,0} &= 1 \\ dp_{0,1} &= 1 \\ \vdots \\ dp_{0,N-1} &= 1 \\ \end{aligned} $$
This time, we’ll do push DP. First, when $s_i$ is >, we can select numbers from $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} $$
Next, when $s_i$ is <, we can select numbers from $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
Let $S$ be a bitmap holding a set of rabbits. Since there are at most 16 rabbits, the calculation is feasible. $dp_S$ is the maximum score when grouping the rabbits in set $S$. Note that $sum(S)$ is the score when $S$ is made into one group.
$$ \begin{aligned} dp_{\phi} &= 0 \\ dp_{S} &= max_{U \subset S} (dp_U + sum(S-U)) \\ \end{aligned} $$
Here, the enumeration of subsets needs to be done cleverly. Simple enumeration takes $O(2^N \cdot 2^N)$, but with clever techniques it can be reduced to $O(3^N)$.
for (S = 1; S < (1 << N); S++) {
for (U = (S-1) & S; ; U = (U-1) & S) {
// DP update process
...
if (U == 0)
break;
}
}
R - Walk
Let $dp_{k,i,j}$ be the number of path patterns to move from vertex $i$ to vertex $j$ with length $2^k$.
$$ \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
Assign indices $0,1, …, N-1$ sequentially from the upper digits of $K$. Let $dp_{i,j,s}$ be the number of patterns where the remainder is $s$ when looking at up to the $i$-th digit. Note that $j=1$ when the first $i$ digits completely match $K$. We’ll do push DP. First, the initial values are as follows:
$$ \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} $$
The update formula differs depending on whether we push from $dp_{i,0,s}$ or $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} $$