ABC 410
Table of Contents
https://atcoder.jp/contests/abc410
A. G1
https://atcoder.jp/contests/abc410/tasks/abc410_a
B. Reverse Proxy
https://atcoder.jp/contests/abc410/tasks/abc410_b
C. Rotatable Array
https://atcoder.jp/contests/abc410/tasks/abc410_c
D. XOR Shortest Walk
https://atcoder.jp/contests/abc410/tasks/abc410_d
コンテスト中考えていたこと
$W_i < 2^{10}$ であるから、各頂点に到達した際の値はせいぜい $2^{10} = 1024$ 通りの値しかない。 頂点 $1$ から始めて各頂点に到達した際の値が新規であれば次の頂点に進み、すでに到達した値であればその頂点で止めるような処理を DFS で行えば良さそう。
親の方向に帰るのは無意味だと思ったけど有向グラフで行きと帰りで重みが違うことがあるから親に帰ることもありえるということを WA を出して気づいた。
計算量的に行けるか不安ではあったが辺の数が少ないので行けるかなぁと思って出したら AC した。
解説によると頂点倍化という手法らしい。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, M;
cin >> N >> M;
using P = pair<ll, ll>;
vector<vector<P>> graph(N);
rep(i, M) {
ll u, v, w;
cin >> u >> v >> w;
u--, v--;
graph[u].emplace_back(v, w);
}
vector used(N, vint(1 << 10, 0));
used[0][0] = true;
auto dfs = [&](auto dfs, int now, ll xor_sum) -> void {
for (auto [nx, w] : graph[now]) {
ll nx_xor_sum = xor_sum ^ w;
if (used[nx][nx_xor_sum]) continue;
used[nx][nx_xor_sum] = true;
dfs(dfs, nx, nx_xor_sum);
}
};
dfs(dfs, 0, 0);
ll ans = INF;
rep(i, 1 << 10) {
if (used[N - 1][i]) chmin(ans, i);
}
if (ans == INF) ans = -1;
cout << ans << endl;
}
E. Battles in a Row
https://atcoder.jp/contests/abc410/tasks/abc410_e
解説 AC.
$dp(i,m)$ を $i$ 番目までのモンスターを倒し時の残りの魔力が $m$ のときの体力の最大値とする。
$dp(i,m) = \max(dp(i-1, m+B_i), dp(i-1,m)-A_i)$
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, H, M;
cin >> N >> H >> M;
vll A(N + 1), B(N + 1);
rep(i, N) cin >> A[i + 1] >> B[i + 1];
vector dp(N + 1, vll(M + 1, -1));
dp[0][M] = H;
rep2(i, 1, N + 1) {
rep(m, M + 1) {
if (m + B[i] <= M) {
chmax(dp[i][m], dp[i - 1][m + B[i]]);
}
chmax(dp[i][m], dp[i - 1][m] - A[i]);
}
}
ll ans = 0;
rep(i, N + 1) rep(m, M + 1) {
if (dp[i][m] >= 0) ans = i;
}
cout << ans << endl;
}
F. Balanced Rectangles
https://atcoder.jp/contests/abc410/tasks/abc410_f