ABC 408
Table of Contents
https://atcoder.jp/contests/abc408
A. Timeout
https://atcoder.jp/contests/abc408/tasks/abc408_a
B. Compression
https://atcoder.jp/contests/abc408/tasks/abc408_b
C. Not All Covered
https://atcoder.jp/contests/abc408/tasks/abc408_c
D. Flip to Gather
https://atcoder.jp/contests/abc408/tasks/abc408_d
コンテスト中に問題文の意味が全く理解できなかった。終了10分前くらいにようやく理解したが結局実装できなかった。 コンテスト終了後2時間近く考えたが結局 AC できなかったのでコンテスト中に問題文の意味が理解できていたとしてもやはり AC できなかっただろう。 解説読んでも理解できなかったのでかなり苦手な問題だったと思う。
解説 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto _cal = []() -> void {
int N;
string S;
cin >> N >> S;
// dp[i][j]: i 番目まで決めて末尾がグループ j に属したときの最小コスト
vvll dp(N + 1, vll(3, INF));
rep(i, 3) dp[0][i] = 0;
rep2(i, 1, N + 1) {
rep(j, 3) {
if (j == 0) {
chmin(dp[i][0], dp[i - 1][0] + (ll)(S[i - 1] == '1'));
}
if (j == 1) {
chmin(dp[i][1], min(dp[i - 1][0], dp[i - 1][1]) + (ll)(S[i - 1] == '0'));
}
if (j == 2) {
chmin(dp[i][2], min(dp[i - 1][0], min(dp[i - 1][1], dp[i - 1][2])) + (ll)(S[i - 1] == '1'));
}
}
}
ll ans = INF;
rep(i, 3) chmin(ans, dp[N][i]);
cout << ans << endl;
};
int t;
cin >> t;
rep(i, t) _cal();
}
E. Minimum OR Path
https://atcoder.jp/contests/abc408/tasks/abc408_e
解説 AC.
考えたこと
bit ごとにどんな経路を辿っても 0 にならない bit は立てざるを得ないから立てて、そうでない場合は極力折りたい。 ただし、単純に bit だけに注目して最適な値を選んでしまうと経路がばらばらで実際には成し遂げられない経路を選択してしまう。 D 問題が全く理解できなかったのでこっちに時間を費やしたが結局うまい解法が思いつかず時間切れ。
解法
$x = 2^{30} - 1$ から初めて上位 bit から順に折ったときに $(x | w_i) = x$ となる辺を選んだときに $1 \sim N$ への経路が存在するかを確認する。 折れる場合は bit を折り、折れない場合はそのままにする。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
vector<tuple<ll, ll, ll>> es;
rep(i, M) {
int u, v, w;
cin >> u >> v >> w;
u--, v--;
es.emplace_back(u, v, w);
}
ll x = (1ll << 30) - 1;
for (int i = 29; i >= 0; i--) {
ll t = x ^ (1ll << i);
dsu uf(N);
for (auto [u, v, w] : es) {
if ((w | t) == t) uf.merge(u, v);
}
if (uf.same(0, N - 1)) {
x = t;
}
}
cout << x << endl;
}
F. Athletic
https://atcoder.jp/contests/abc408/tasks/abc408_f
2026/2/15 segment tree で解けると知って状態で解いたが解説 AC.
segment tree にデータを入れるタイミングを遅延させる
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, D, R;
cin >> N >> D >> R;
vll H(N), hid(N);
rep(i, N) {
cin >> H[i];
H[i]--;
hid[H[i]] = i;
}
auto op = [](ll a, ll b) -> ll { return max(a, b); };
auto e = []() -> ll { return -1; };
segtree<ll, op, e> seg(N);
vll dp(N, -1);
rep(h, N) {
if (h - D >= 0) {
ll j = hid[h - D];
seg.set(j, dp[j]);
}
ll i = hid[h];
ll l = max(0ll, i - R), r = min(N, i + R + 1);
ll mx = seg.prod(l, r);
chmax(dp[i], mx + 1);
}
ll ans = *max_element(all(dp));
cout << ans << endl;
}