とても楽しいコンテストだった。本番は $14$ 完だった。解けていない問題についてはゆっくり更新していく。

A (Frog 1)

今いる位置から飛べる位置への最小コストをまとめる。

$dp[i+1] = min(dp[i+1], dp[i] + |h_i-h_{i+1}|)$
$dp[i+2] = min(dp[i+2], dp[i] + |h_i-h_{i+2}|)$

B (Frog 2)

A とほぼ同じ。遷移先が増えるだけ。

$dp[i+k] = min(dp[i+k], dp[i] + |h_i-h_{i+k}|)\ (k=1, \cdots, K)$

C (Vacation)

$2$ 日連続で同じ活動ができないので、前日に選んだ活動を保持しておいて遷移する。

$f(i, pre) := i$ 日目まで見て直前の活動が $pre$ であるときの最大値とすると前日を同じ場合を除いて

$max(f(i+1, 1)+a[i], f(i+1, 2)+b[i], f(i+1, 3)+c[i])$

が最大値になる。メモ化再帰で解いた。

D (Knapsack 1)

よくあるナップザック

$dp[i][j] := i$ 番目までみて重さが $j$ のときの最大の価値

E (Knapsack 2)

よくあるナップザック

$dp[i][j] := i$ 番目までみて価値が $j$ のときの重さの最小値

F (LCS)

LCSの復元。まだよく理解できていない。

G (Longest Path)

各頂点から dfs したときの有向パスの最大値を解いた。メモ化再帰。

H (Grid 1)

数Ⅰとかででてくるよくある経路の個数の問題。 $dp[i][j] :=$ 位置 $(i, j)\ (0-indexed)$ の場合の数とすると # のマスを除いて

$dp[i+1][j] += dp[i][j]$
$dp[i][j+1] += dp[i][j]$

となる。解は $dp[H-1][W-1]$ となる。

I (Coins)

$dp[i][j] :=$ 表が $i$ 回、裏が $j$ 回出るときの確率とすると

$now = i+j$ として

$dp[i+1][j] += dp[i][j] * p[now]$
$dp[i][j+1] += dp[i][j] * (1-p[now])$

答えは $N \lt 2*i$ なる $i$ について $ans += dp[i][N-i]$ が解になる。

J (Sushi)

解けていない

K (Stones)

ゲーム。WL-Algorithm の雰囲気で解ける。負ける状態に遷移させることができる山の個数の場合は勝ち。そうでない場合は負け。

山に $dp[i] := i$ 個あるときの勝敗とすると

DP初期値は $K=min(a_i)$ として $dp[0], \cdots, dp[K-1]$ までが負けとなる。山から石を選ぶことができないので。 $dp[K]$ 以降は $i-a_j$ 個ある山が負けになる場合が存在する場合は $i$ 個の山は勝ちとなる。それ以外は負け。

L (Deque)

ゲーム。順番が入れ替わることに $max$ と $min$ が入れ替わる。 $1$ 回ごとに選べる区間が小さくなるので、いずれ区間がなくなり最終的な値が決まる。

DPの遷移は

太郎くんの順番の場合は $max(f(l+1, r, 1) + a[l], f(l, r-1, 1) + a[r])$
次郎くんの順番の場合は $min(f(l+1, r, 0) - a[l], f(l, r-1, 0) - a[r])$

となる。メモ化再帰で解いた。

M (Candies)

よく理解できていない。本番は蟻本写した()

N (Slimes)

区間DP。 $rec(l, r) :=$ 区間 $[l, r)$ での最小コストと定義する。そのとき $l \lt k \lt r$ なる $k$ について

$\displaystyle rec(l, r) = min(rec(l, k) + rec(k+1, r) + \sum_{i={l+1}}^{r-1} a_i)$

が成り立つ。区間上の $1$ 点を選ぶと、区間が $2$ つに分かれていき、いずれ区間がなくなり状態が決まる。メモ化再帰で解いた。

O (Matching)

$dp[i][S] :=$ 男性 $i$ について女性の部分集合 $S$ とマッチングするときの場合の数

とする。DPの遷移は $S$ の bit が立っているいずれかの女性とマッチングさせるので配るDPの要領で

$dp[i+1][s\ |\ 1 \lt\lt j] += dp[i][s] (s \in S)$

となる。ナイーブに実装すると $O(N^2*2^N)$ となって間に合わないが、マッチングする候補は $i$ 番目の男性について考える場合は $bitcount(s) == i$ の $s$ のみ考えればよく、計算量が $O(N*2^N)$ に落ちる。

P (Independent Set)

木DP。D - 塗り絵とほぼ同じ。

Q (Flowers)

LIS をセグメントツリーで高速化するDP。

R (Walk)

$0$ 回目に各頂点 $i (1 \le i \le N)$ に存在する場合の数を $(1,1,\cdots,1)$ とすると、 $k$ 回目のそれぞれの頂点にいる場合の数は $(1,1,\cdots,1)$ に行列 $A$ を $K$ 回掛けた結果になる。よって $A$ の $mod$ 上の行列累乗を求めておけば解くことができる。(ナイーブに行列 $A$ を $K$ 回掛けるのは TLE になる)

S (Digit Sum)

よくある桁DP。 $f(i, j, tight) := i$ 桁目まで考えたとき、 $D$ の余りが $j$ で今ピッタリかどうか $tight$ と見ると解ける。メモ化再帰。

T (Permutation)

解けていない。

U (Grouping)

集合が $2$ つに分かれていくDP。まだ詳細に理解していない。

V (Subtree)

解けていない。

W (Intervals)

解けていない。

X (Tower)

解けていない。

Y (Grid 2)

$dp[i] := i-1$ 個までの点を通らず $i$ 個目の点を通る場合の数

とDPを定義する。DPの遷移は点 $i$ よりも左上にある点を $j$ とすると

$\displaystyle dp[i] = {}_{r_i-1+c_i-1} \mathrm{C}_{r_i-1} - \sum (dp[j] * {}_{r_i - r_j + c_i - c_j} \mathrm{C}_{r_i - r_j} )$

となる。解は $dp[N]$ である。

$N$ つの点を通らずマス $(H,W)$ への経路は、マス $(H,W)$ への経路 $-\ N$ つの点を $1$ つでも通る場合の数 であることから包除原理より求めることができる。左上にある点集合を $O(N)$ で求めるには、事前に $N$ つの点を $(r_i+c_i)$ の昇順でソートしておけばよい。