EDPCメモ

AtCoderのEducational DP Contestを全部通したので、自力で解けなかった問題や時間がかかった問題のメモを残しておこうと思います。

EDPC完走！ pic.twitter.com/zasWHVVspi

— けんしん (@knshnb) March 21, 2019

R - Walk

グラフのパスの総数は、隣接行列の掛け算で得られる。
解けそうにない問題は制約とかから行列累乗を疑ってみるのはあり。

S - Digit Sum

桁DP
dp[i][j][k]... : i番目まで見たときの保存したい値、j,kなどにgirigiriかどうかのflagを持たせる

REP (d, (j ? 9 : S[i] - '0') + 1) {
  // ...

をよく使う。

U - Grouping

$2^n$個の状態があり、遷移に2つの部分集合のマージが必要なため$\mathcal{O}(3^n)$になるbitDP。
計算量は、 $$\sum_{k = 0}^n 2^k nCk = (2 + 1)^n$$ でもわかるし、ループの一番内側が各要素について(S / not S, T / not S, not T)の3種類回っていることからもわかる。

$S$の部分集合の列挙は、

for (int T = S;; T = (T - 1) & S) {
  // 操作
  if (T == 0) break;
}

でできる。

V - Subtree

全方位木DPはそれなりに慣れているはずだったが時間がかかり、通すのが最後になってしまった。

モノイド(逆元が求められない)上の列について、$\mathcal{O}(n)$で各要素$i$についてそれ以外の要素の畳込みををすべて求める部分が難しい。
これは正方向の累積と逆方向の累積を計算しておけばできる。

W - Intervals

一番難しく感じた。完全に解説を見てしまった。

区間がたくさん与えられる問題は(左/右でソート) * (左/右から見ていく)の4通りをとりあえず考える。
右でソートして左から見ていきながら、
dp[i]: 1番右の1がi番目である中のmax
を更新していけばできる。

X - Tower

$i$番目と$j$番目のブロックどちらかを先に置くかを決められないか考える。 既に置かれている重さの合計を$W$として、

• $i$の次に$j$ : $W + w_i <= s_j \Leftrightarrow W <= s_j - w_i$
• $j$の次に$i$ : $W + w_j <= s_i \Leftrightarrow W <= s_i - w_j$

右辺を見比べて、 $$s_j - w_i >= s_i - w_j \Leftrightarrow s_i + w_i <= s_j + w_j$$ のとき、$i$の次に$j$をおいた方がが必ず得をする。
これは推移律を満たすので$s + w$でソートしてdpすればよい。

式変形したらこうなるのはわかるんだけど直感的にあんまりしっくり来ていない、 誰か直感的な説明があったら教えてください…

追記

@beet_aizuさんに直感的な証明を教えていただきました。 こんなのどうやったら思いつくんですかね…

Y - Grid 2

除DPというらしい。
はじめ包除原理を考えたが計算量的に無理だった。
各状態で初めて満たしているものを貪欲にDPの値として保存していく(前に使ったものは取り除く)とうまくいくことがある。

Z - Frog 3

CHTの典型っぽい。
$(h_i - h_j)^2$を展開したときに2乗の項が各地点において定数とみなせるのがポイント。
以下をパクった。
http://kazuma8128.hatenablog.com/entry/2018/02/28/102130

その他知見

• 区間DPなど、トポロジカル順が自明でないものはメモ化再帰で書くと思考停止で書ける。
• bitDPは個人的にはfor文で書くほうがラク。