コンテストのリンク
今更過ぎるけど全部解いたので提出コードや感想メモなど。
A - Frog 1
#include "my_template.hpp"
using namespace std;
void solve() {
INT(N);
VEC(i64, A, N);
vector<i64> dp(N, INF<i64>);
dp[0] = 0;
REP(i, N - 1) {
if (i + 1 < N) chmin(dp[i + 1], dp[i] + abs(A[i] - A[i + 1]));
if (i + 2 < N) chmin(dp[i + 2], dp[i] + abs(A[i] - A[i + 2]));
}
print(dp[N - 1]);
return;
}
int main() {
solve();
return 0;
}
B - Frog 2
#include "my_template.hpp"
using namespace std;
void solve() {
INT(N, K);
VEC(i64, A, N);
vector<i64> dp(N, INF<i64>);
dp[0] = 0;
REP(i, N) {
REP(k, 1, K + 1) {
if (i + k < N) chmin(dp[i + k], dp[i] + abs(A[i] - A[i + k]));
}
}
print(dp[N - 1]);
return;
}
int main() {
solve();
return 0;
}
C - Vacation
#include "my_template.hpp"
using namespace std;
void solve() {
INT(N);
VV(i64, a, N, 3);
vector dp(3, vector<i64>(N + 1, -INF<i64>));
REP(k, 3) dp[k][0] = 0;
REP(i, N) {
REP(j, 3) {
REP(k, 3) {
if (j == k) continue;
chmax(dp[k][i + 1], dp[j][i] + a[i][k]);
}
}
}
i64 ans = -INF<i64>;
REP(k, 3) chmax(ans, dp[k][N]);
print(ans);
return;
}
int main() {
solve();
return 0;
}
D - Knapsack 1
#include "my_template.hpp"
using namespace std;
void solve() {
INT(N, W);
VEC2(i64, w, v, N);
vector dp(W + 1, -INF<i64>);
dp[0] = 0;
REP(i, N) RREP(j, W + 1 - w[i]) chmax(dp[j + w[i]], dp[j] + v[i]);
print(MAX(dp));
return;
}
int main() {
solve();
return 0;
}
E - Knapsack 2
#include "my_template.hpp"
using namespace std;
void solve() {
INT(N, W);
VEC2(i64, w, v, N);
constexpr int V = 1000 * 100;
vector dp(V + 1, INF<i64>);
dp[0] = 0;
REP(i, N) RREP(j, V + 1 - v[i]) chmin(dp[j + v[i]], dp[j] + w[i]);
i64 ans = 0;
REP(j, V + 1) if (dp[j] <= W) ans = j;
print(ans);
return;
}
int main() {
solve();
return 0;
}
F - LCS
（この機会にLCSライブラリを作ったのは内緒。）
#include "my_template.hpp"
#include "dp/longest_common_subsequence.hpp"
using namespace std;
void solve() {
STR(s, t);
print(longest_common_subsequence(s, t));
return;
}
int main() {
solve();
return 0;
}
G - Longest Path
DAGに対してはTopological Sortするという典型。
#include "my_template.hpp"
#include "graph/read_graph.hpp"
#include "graph/topological_sort.hpp"
using namespace std;
void solve() {
INT(N, M);
auto g = read_graph<int>(N, M, false, true);
auto vs = topological_sort(g);
vector<int> dp(N);
FORE(v, vs) FORE(e, g[v]) chmax(dp[e.to], dp[v] + 1);
print(MAX(dp));
return;
}
int main() {
solve();
return 0;
}
H - Grid 1
#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;
void solve() {
INT(H, W);
VEC(string, a, H);
vector dp(H, vector<mint>(W));
dp[0][0] = 1;
REP(i, H) REP(j, W) {
if (a[i][j] == '#') continue;
if (i + 1 < H) dp[i + 1][j] += dp[i][j];
if (j + 1 < W) dp[i][j + 1] += dp[i][j];
}
print(dp[H - 1][W - 1]);
return;
}
int main() {
solve();
return 0;
}
I - Coins
FPSでも解ける。
#include "my_template.hpp"
using namespace std;
void solve() {
INT(N);
VEC(f64, p, N);
vector<f64> dp(2 * N + 1);
dp[N] = 1;
REP(i, N) {
vector<f64> np(2 * N + 1);
REP(j, 2 * N + 1) {
if (j + 1 < 2 * N + 1) np[j + 1] += dp[j] * p[i];
if (j - 1 >= 0) np[j - 1] += dp[j] * (1 - p[i]);
}
swap(dp, np);
}
f64 ans = 0;
REP(i, 2 * N + 1) if (i - N > 0) ans += dp[i];
print(ans);
return;
}
int main() {
solve();
return 0;
}
J - Sushi
#include "my_template.hpp"
using namespace std;
void solve() {
INT(N);
VEC(int, a, N);
vector<int> x(4);
REP(i, N) x[a[i]]++;
vector dp(N + 1, vector(N + 1, vector<f64>(N + 1)));
vector memo(N + 1, vector(N + 1, vector<int>(N + 1)));
auto rec = [&](auto f, int x1, int x2, int x3) -> f64 {
if (memo[x1][x2][x3]) return dp[x1][x2][x3];
if (x1 == 0 and x2 == 0 and x3 == 0) return 0;
memo[x1][x2][x3] = 1;
if (x1 > 0) dp[x1][x2][x3] += (f(f, x1 - 1, x2, x3) + 1) * x1 / N;
if (x2 > 0) dp[x1][x2][x3] += (f(f, x1 + 1, x2 - 1, x3) + 1) * x2 / N;
if (x3 > 0) dp[x1][x2][x3] += (f(f, x1, x2 + 1, x3 - 1) + 1) * x3 / N;
dp[x1][x2][x3] += (f64(N) - x1 - x2 - x3) / N;
dp[x1][x2][x3] *= f64(N) / (x1 + x2 + x3);
return dp[x1][x2][x3];
};
print(rec(rec, x[1], x[2], x[3]));
return;
}
int main() {
solve();
return 0;
}
K - Stones
#include "my_template.hpp"
using namespace std;
void solve() {
INT(N, K);
VEC(int, A, N);
vector<int> dp(K + 1);
REP(k, 1, K + 1) {
FORE(x, A) {
if (k - x >= 0 and dp[k - x] == 0) {
dp[k] = 1;
}
}
}
First(dp[K]);
return;
}
int main() {
solve();
return 0;
}
L - Deque
区間DP。
未だに区間DPはメモ化再帰でしか書いたことがない気がする…。
#include "my_template.hpp"
using namespace std;
void solve() {
INT(N);
VEC(i64, A, N);
vector dp(N + 1, vector<i64>(N + 1));
vector memo(N + 1, vector<int>(N + 1));
auto rec = [&](auto f, int l, int r) -> i64 {
if (memo[l][r]) return dp[l][r];
if (l == r) return 0;
int used = N - (r - l);
memo[l][r] = 1;
if (used % 2 == 0) {
dp[l][r] = max(f(f, l + 1, r) + A[l], f(f, l, r - 1) + A[r - 1]);
} else {
dp[l][r] = min(f(f, l + 1, r) - A[l], f(f, l, r - 1) - A[r - 1]);
}
return dp[l][r];
};
print(rec(rec, 0, N));
return;
}
int main() {
solve();
return 0;
}
M - Candies
累積和で高速化するDP。
昔は累積和の添字合わせに苦労していたけどさすがに今はかなり減ってきた。
#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;
void solve() {
INT(N, K);
VEC(int, A, N);
vector<mint> dp(K + 1);
dp[K] = 1;
REP(i, N) {
vector<mint> cp(K + 2);
REP(j, K + 1) cp[j + 1] = cp[j] + dp[j];
vector<mint> np(K + 1);
REP(j, K + 1) {
np[j] = cp[min(j + A[i] + 1, K + 1LL)] - cp[j];
}
swap(dp, np);
}
print(dp[0]);
return;
}
int main() {
solve();
return 0;
}
N - Slimes
区間DP。
#include "my_template.hpp"
using namespace std;
void solve() {
INT(N);
VEC(i64, A, N);
vector dp(N + 1, vector<i64>(N + 1, INF<i64>));
vector memo(N + 1, vector<int>(N + 1));
vector<i64> ac(N + 1);
REP(i, N) ac[i + 1] = ac[i] + A[i];
auto rec = [&](auto f, int l, int r) -> i64 {
if (memo[l][r] == 1) return dp[l][r];
if (r - l == 1) return dp[l][r] = 0;
memo[l][r] = 1;
for (int k = l + 1; k < r; k++) {
chmin(dp[l][r], f(f, l, k) + f(f, k, r) + ac[r] - ac[l]);
}
return dp[l][r];
};
i64 ans = rec(rec, 0, N);
print(ans);
return;
}
int main() {
solve();
return 0;
}
O - Matching
bitDP。
#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;
void solve() {
INT(N);
VV(int, A, N, N);
const int N2 = 1 << N;
vector<mint> dp(N2);
dp[0] = 1;
REP(bit, N2) {
int pc = popcnt(bit);
REP(i, N) {
if (IBIT(bit, i)) continue;
if (A[pc][i]) {
dp[bit | (1 << i)] += dp[bit];
}
}
}
print(dp[N2 - 1]);
return;
}
int main() {
solve();
return 0;
}
P - Independent Set
木DP。
#include "my_template.hpp"
#include "graph/read_graph.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;
void solve() {
INT(N);
auto g = read_graph<int>(N, N - 1);
vector dp(2, vector<mint>(N, 1));
auto rec = [&](auto f, int cur, int par) -> void {
FORE(e, g[cur]) {
if (e.to == par) continue;
f(f, e.to, cur);
dp[1][cur] *= dp[0][e.to];
dp[0][cur] *= dp[0][e.to] + dp[1][e.to];
}
};
rec(rec, 0, -1);
mint ans = dp[0][0] + dp[1][0];
print(ans);
return;
}
int main() {
solve();
return 0;
}
Q - Flowers
データ構造（Segment Tree）を使うDP。
#include "my_template.hpp"
#include "data_structure/segment_tree.hpp"
#include "algebra/monoid_s/monoid_max.hpp"
using namespace std;
void solve() {
INT(N);
VEC(int, h, N);
VEC(i64, a, N);
REP(i, N) h[i]--;
SegmentTree<MonoidMax<i64>> seg(N);
REP(i, N) {
i64 mx = seg.prod(0, h[i]);
chmax(mx, 0);
seg.set(h[i], mx + a[i]);
}
print(seg.all_prod());
return;
}
int main() {
solve();
return 0;
}
R - Walk
ダブリングを使うDP。
#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;
void solve() {
I64(N, K);
VV(int, A, N, N);
vector db(60, vector(N, vector<mint>(N)));
REP(i, N) REP(j, N) db[0][i][j] = A[i][j];
REP(b, 59) REP(i, N) REP(j, N) REP(k, N) db[b + 1][i][j] += db[b][i][k] * db[b][k][j];
vector dp(N, vector<mint>(N));
REP(i, N) dp[i][i] = 1;
REP(b, 60) {
if (IBIT(K, b)) {
vector np(N, vector<mint>(N));
REP(i, N) REP(j, N) REP(k, N) np[i][j] += dp[i][k] * db[b][k][j];
swap(dp, np);
}
}
mint ans = 0;
REP(i, N) ans += SUM(dp[i], mint(0));
print(ans);
return;
}
int main() {
solve();
return 0;
}
S - Digit Sum
桁DP。
#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;
void solve() {
STR(S);
INT(D);
vector dp(2, vector<mint>(D));
dp[0][0] = 1;
const int N = LEN(S);
REP(i, N) {
vector np(2, vector<mint>(D));
REP(j, 2) {
REP(k, D) {
const int ud = j ? 9 : S[i] - '0';
REP(d, ud + 1) np[j | (d < S[i] - '0')][(k + d) % D] += dp[j][k];
}
}
swap(dp, np);
}
mint ans = dp[0][0] + dp[1][0] - 1;
print(ans);
return;
}
int main() {
solve();
return 0;
}
T - Permutation
挿入DP。
昔解説ACした記憶がある。
昔はどのあたりが挿入なのかわからなかったが、今は「残っている数の集合から1つを抜き取って数列の末尾に付け加える」様子が挿入っぽいという理解をしている。
#include "my_template.hpp"
#include "math/static_modint.hpp"
using mint = mint107;
using namespace std;
void solve() {
INT(N);
STR(S);
vector<mint> dp(N);
REP(i, N) {
dp[i] = 1;
}
REP(i, N - 1) {
vector<mint> np(N - 1 - i);
vector<mint> cp(N + 1 - i);
REP(j, N - i) cp[j + 1] = cp[j] + dp[j];
if (S[i] == '<') {
REP(j, N - 1 - i) {
np[j] = cp[j + 1] - cp[0];
}
} else {
REP(j, N - 1 - i) {
np[j] = cp[N - i] - cp[j + 1];
}
}
swap(dp, np);
}
mint ans = SUM(dp, mint(0));
print(ans);
return;
}
int main() {
solve();
return 0;
}
U - Grouping
bitDP。
要素からなる集合のべき集合について、各要素の部分集合を償却計算量 
で列挙するテクニックを使う。
#include "my_template.hpp"
using namespace std;
void solve() {
INT(N);
VV(i64, A, N, N);
const int N2 = 1 << N;
vector<i64> dp(N2);
REP(bit, N2) {
REP(j, N) {
if (IBIT(bit, j) == 0) continue;
REP(i, j) {
if (IBIT(bit, i) == 0) continue;
dp[bit] += A[i][j];
}
}
}
REP(bit, N2) FORSUB(s, bit) chmax(dp[bit], dp[bit ^ s] + dp[s]);
print(dp[N2 - 1]);
return;
}
int main() {
solve();
return 0;
}
V - Subtree
全方位木DP。
任意 
であるため、この問題はDPで求めるものがモノイドであり群ではない（=逆元があるとは限らない）。
よって累積和を持つ必要があり、実装が大変。
抽象化ライブラリを作りたいなと思いつつもまだできていない。
#include "my_template.hpp"
#include "graph/read_graph.hpp"
#include "math/dynamic_modint.hpp"
using mint = mintd;
using namespace std;
void solve() {
INT(N, M);
mint::set_mod(M);
auto g = read_graph<int>(N, N - 1);
vector dp_cuml(2, vector<vector<mint>>(N));
vector dp_cumr(2, vector<vector<mint>>(N));
auto rec = [&](auto f, int cur, int par) -> void {
FORE(e, g[cur]) {
if (par == e.to) continue;
f(f, e.to, cur);
}
dp_cuml[0][cur].assign(LEN(g[cur]) + 1, 1);
dp_cuml[1][cur].assign(LEN(g[cur]) + 1, 1);
dp_cumr[0][cur].assign(LEN(g[cur]) + 1, 1);
dp_cumr[1][cur].assign(LEN(g[cur]) + 1, 1);
REP(i, LEN(g[cur])) {
auto e = g[cur][i];
if (par == e.to) {
dp_cuml[0][cur][i + 1] = dp_cuml[0][cur][i];
dp_cuml[1][cur][i + 1] = dp_cuml[1][cur][i];
} else {
dp_cuml[0][cur][i + 1] = dp_cuml[0][cur][i] * dp_cuml[0][e.to].back();
dp_cuml[1][cur][i + 1] = dp_cuml[1][cur][i] * (dp_cuml[0][e.to].back() + dp_cuml[1][e.to].back());
}
}
RREP(i, LEN(g[cur])) {
auto e = g[cur][i];
if (par == e.to) {
dp_cumr[0][cur][i] = dp_cumr[0][cur][i + 1];
dp_cumr[1][cur][i] = dp_cumr[1][cur][i + 1];
} else {
dp_cumr[0][cur][i] = dp_cumr[0][cur][i + 1] * dp_cuml[0][e.to].back();
dp_cumr[1][cur][i] = dp_cumr[1][cur][i + 1] * (dp_cuml[0][e.to].back() + dp_cuml[1][e.to].back());
}
}
};
rec(rec, 0, -1);
vector dp_all(2, vector<mint>(N));
auto rerooting = [&](auto f, int cur, int par, mint dp_par0, mint dp_par1) -> void {
dp_all[0][cur] = dp_cuml[0][cur].back() * dp_par0;
dp_all[1][cur] = dp_cuml[1][cur].back() * (dp_par0 + dp_par1);
REP(i, LEN(g[cur])) {
auto e = g[cur][i];
if (par == e.to) continue;
mint dp_cur0 = dp_cuml[0][cur][i] * dp_cumr[0][cur][i + 1] * dp_par0;
mint dp_cur1 = dp_cuml[1][cur][i] * dp_cumr[1][cur][i + 1] * (dp_par0 + dp_par1);
f(f, e.to, cur, dp_cur0, dp_cur1);
}
};
rerooting(rerooting, 0, -1, 1, 0);
REP(i, N) print(dp_all[1][i]);
return;
}
int main() {
solve();
return 0;
}
W - Intervals
文字列に含まれる 1 のうち、最も後ろにあるものが 
文字目であるもののスコアの最大値
とし、
と順番に計算する。
を計算する際には、
から遷移するが、スコアの重複加算を避ける必要がある。
文字目を 1 にすることによっても得られるスコア（つまり、
である 
に対する 
のスコア）は 
にはまだ加算されていない状況にしておけば、単に の最大値を取ってきて、 を加算することで求めることができる。
ところでここで求めた についても、
以降の計算で利用するときにはまだこの の分のスコアが加算されていない状況にしておく必要がある。
結局のところ、スコアの確定が遅れるイメージで、スコアの重複加算が発生しないところまで計算したら区間加算を行えば良い。
区間加算が必要なのでLazy Segment Treeを使う。
イメージとしてはLISやQ - Flowersに似ているのだが、こういう配列を使い回すDP全般のことをインラインDPと呼ぶらしい。
#include "my_template.hpp"
#include "data_structure/lazy_segment_tree.hpp"
#include "algebra/monoid_s_f/monoid_max_add.hpp"
using namespace std;
void solve() {
INT(N, M);
VEC3(i64, L, R, A, M);
REP(i, M) L[i]--;
LazySegmentTree<MonoidMaxAdd<i64>> seg(N + 1);
seg.set(0, 0);
vector<vector<int>> gr(N + 1);
REP(i, M) gr[R[i]].push_back(i);
REP(i, N) {
i64 mx = seg.prod(0, i + 1);
seg.set(i + 1, mx);
FORE(ind, gr[i + 1]) seg.apply(L[ind] + 1, R[ind] + 1, A[ind]);
}
print(seg.all_prod());
return;
}
int main() {
solve();
return 0;
}
X - Tower
どのブロックを使ったかを集合で管理しては状態数が多すぎるため、うまく減らすことを考える。
ある順序でブロックを並べ、各ブロックを塔の下に繋げるかを決めていくことにする。
こうすると、繋げられるかを判定する際には、それまでに使ったブロックの重さの総和だけわかれば良く、状態数の削減ができている。（順序がないものに対して順序を導入することで状態数を減らすという考え方）
ではどのような順序でブロックを並べれば良いのかというと、結論としては 
の小さい順に並べれば良い。
証明の方針としては
隣接するブロック
について、
であるとき、入れ替えても損をしない
最適解の中に の小さい順に並んだものがあるので、この順番でブロックを塔の下に繋げるかを決めていくことにしても良い
という流れ。
↑本当は専門書を読んだほうが良いのだが…
入れ替えられることを示すためには、ブロック の上に積み上がっているブロックの総重量を 
として
から
を示せば良い。
1つ目は 
より成立。
2つ目は 
より成立。
損をしないというのは、他のブロックが積み重ねられるかに影響を与えないことからわかる。
より正確には、ブロック より上のブロックについては下がどうなってるかはどうでも良く、ブロック より下のブロックについては入れ替え前後で自分より上のブロックの総重量は変化しないため。
ちなみにこの比較関数自体は、2つ目の条件である 
を示すためにはどういう条件が必要かを考えることで導出できる。
までは言えているわけで、最右辺の 
を睨むと出てくるように思う。
#include "my_template.hpp"
using namespace std;
void solve() {
INT(N);
VEC3(i64, w, s, v, N);
vector<int> inds(N);
iota(ALL(inds), 0);
sort(ALL(inds), [&](int i, int j) { return s[i] + w[i] < s[j] + w[j]; });
constexpr int W = 20000;
vector<i64> dp(W + 1, -INF<i64>);
dp[0] = 0;
FORE(i, inds) {
auto np = dp;
REP(j, s[i] + 1) {
if (dp[j] == -INF<i64>) continue;
if (j + w[i] > W) continue;
chmax(np[j + w[i]], dp[j] + v[i]);
}
swap(dp, np);
}
i64 ans = MAX(dp);
print(ans);
return;
}
int main() {
solve();
return 0;
}
Y - Grid 2
解説ACした。包除原理を使う。
壁のマスを一旦無視してすべての移動経路数を数え上げ、壁マスを通る移動経路数を引けば良い。
壁マスを通る移動経路数を求める際に、初めて通る壁マスがどれかで場合分けする。
右か下にしか移動しないため、
が小さい順に訪れるはずであり、その順でソートする。
あとはコード中のコメントを参照すればわかりそう。
#include "my_template.hpp"
#include "math/static_modint.hpp"
#include "math/binomial.hpp"
using mint = mint107;
using namespace std;
void solve() {
Binomial<mint> B;
INT(H, W, N);
VEC2(int, x, y, N);
REP(i, N) x[i]--, y[i]--;
vector<int> inds(N);
iota(ALL(inds), 0);
sort(ALL(inds), [&](int i, int j) { return x[i] + y[i] < x[j] + y[j]; });
vector<mint> dp(N);
mint ans = 0;
REP(i, N) {
int ind = inds[i];
dp[i] = B.C(x[ind] + y[ind], x[ind]);
REP(j, i) dp[i] -= dp[j] * B.C(x[ind] - x[inds[j]] + y[ind] - y[inds[j]], x[ind] - x[inds[j]]);
ans += dp[i] * B.C(H - 1 - x[ind] + W - 1 - y[ind], H - 1 - x[ind]);
}
ans = B.C(H - 1 + W - 1, H - 1) - ans;
print(ans);
return;
}
int main() {
solve();
return 0;
}
Z - Frog 3
Convex Hull Trickを使う。
を変形すると
であり、
は によらない。
は よく見ると 
の1次関数になっている。
ei1333さんのライブラリ を借りて実装した。
#include "my_template.hpp"
using namespace std;
void solve() {
I64(N, C);
VEC(i64, h, N);
DynamicLiChaoTree<i64, 0, 1000000, INF<i64>> cht;
vector<i64> dp(N, INF<i64>);
dp[0] = 0;
cht.add_line(-2 * h[0], h[0] * h[0] + dp[0]);
REP(i, 1, N) {
i64 mn = cht.query(h[i]);
dp[i] = mn + h[i] * h[i] + C;
cht.add_line(-2 * h[i], dp[i] + h[i] * h[i]);
}
print(dp[N - 1]);
return;
}
int main() {
solve();
return 0;
}
感想
TおよびV〜Zが特に勉強になった。（序盤もおそらく勉強になったのだろうけど、初めて解いた時に比べて実力が上がりすぎてもう良くわからない。）
最近は一周回ってこういう単元別問題集みたいなものを埋めていこうという気持ちになっているので、頑張りたい。
