ABC 447
Table of Contents
https://atcoder.jp/contests/abc447
A. Seats 2
https://atcoder.jp/contests/abc447/tasks/abc447_a
2026/2/28 コンテスト中に自力 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, M;
cin >> N >> M;
vint v(N);
for (int i = 0; i < N; i += 2) {
v[i] = 1;
}
int sum = accumulate(all(v), 0);
yesno(sum >= M);
}
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, M;
cin >> N >> M;
yesno(M <= ceil(N, 2));
}
B. mpp
https://atcoder.jp/contests/abc447/tasks/abc447_b
2026/2/28 コンテスト中に自力 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string S;
cin >> S;
map<char, int> mp;
for (auto c : S) mp[c]++;
int mx = 0;
for (auto [k, v] : mp) chmax(mx, v);
string ans = "";
for (char c : S) {
if (mp[c] == mx) continue;
ans.pb(c);
}
cout << ans << endl;
}
C. Insert and Erase A
https://atcoder.jp/contests/abc447/tasks/abc447_c
2026/2/28 コンテスト中に自力 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string S, T;
cin >> S >> T;
{
string s, t;
for (char c : S)
if (c != 'A') s.pb(c);
for (char c : T)
if (c != 'A') t.pb(c);
// A を抜いた文字列が一致しない場合はどうやっても無理
if (s != t) {
cout << -1 << endl;
return;
}
}
S.pb('_'); // sentinel
int sn = S.size(), tn = T.size();
int ans = 0;
int si = 0, ti = 0;
while (ti < tn) {
while (T[ti] != 'A' && S[si] == 'A') { // S の A を消す
si++;
ans++;
}
while (T[ti] == S[si]) {
ti++;
si++;
continue;
}
if (T[ti] == 'A') { // S に A を挿入
ti++;
ans++;
}
}
// S の余剰の A を消す
ans += sn - si - 1; // -1 は sentinel 分
cout << ans << endl;
}
D. Take ABC 2
https://atcoder.jp/contests/abc447/tasks/abc447_d
2026/2/28 コンテスト中に自力 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string S;
cin >> S;
// A: ペアになっていない A の数
// AB: (A, B) のペアになっている数
int A = 0, AB = 0;
int ans = 0;
int N = S.size();
rep(i, N) {
char c = S[i];
if (c == 'A') {
A++;
} else if (c == 'B' && A) {
A--;
AB++;
} else if (c == 'C' && AB) {
AB--;
ans++;
}
}
cout << ans << endl;
}
E. Divide Graph
https://atcoder.jp/contests/abc447/tasks/abc447_e
2026/2/28 コンテスト後に自力 AC
$i$ 番目の辺を消すコストは $2^i$ だからなるべく後半にある辺はなるべく残したい。
辺を張っていない状態から辺を張っていくことを考える。 連結していない頂点同士を結ぶと全体の連結成分数が1つ減る。 よって後半の辺から張っていき、連結成分数が2以下になったらそれ以降で連結成分が減ってしまう辺は張らないようにする。 このときの張らなかった辺の index を記録しておき、最後に $2^i$ を足し合わせれば答えになる。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
using P = pair<int, int>;
vector<P> ps;
rep(i, M) {
int u, v;
cin >> u >> v;
u--, v--;
ps.emplace_back(u, v);
}
vector<mint> twopow(M + 1);
twopow[0] = 1;
rep2(i, 1, M + 1) twopow[i] = twopow[i - 1] * 2;
dsu uf(N);
vint del;
ll cnt = N;
for (int i = M - 1; i >= 0; i--) {
auto [u, v] = ps[i];
if (uf.same(u, v))
continue;
if (cnt > 2) {
uf.merge(u, v);
cnt--;
} else {
del.pb(i + 1);
}
}
mint ans = 0;
for (ll x : del) {
ans += twopow[x];
}
cout << ans.val() << endl;
}
F. Centipede Graph
https://atcoder.jp/contests/abc447/tasks/abc447_f
ムカデグラフとなる部分を抜き出してきて木の直径を求めるということはわかったが、直径を求める部分でバグらせてしまった。
2026/3/1 解説AC
解説放送を見て実装。まだ自分の言葉にできていないので完全に理解はできていない。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
auto cal = []() -> void {
int N;
cin >> N;
vvint graph(N);
rep(i, N - 1) {
int a, b;
cin >> a >> b;
a--, b--;
graph[a].pb(b);
graph[b].pb(a);
}
ll ans = 1;
auto dfs = [&](auto dfs, int now, int p = -1) -> ll {
ll deg = graph[now].size();
ll mx = 0;
for (ll nx : graph[now]) {
if (nx == p) continue;
ll r = dfs(dfs, nx, now);
if (deg >= 4) chmax(ans, mx + r + 1); // now から2方向に伸ばしたときの最大値
if (deg >= 3) chmax(ans, r + 1); // now から1方向に伸ばしたときの最大値
chmax(mx, r);
}
// 返り値は now から伸びるパスの最大長を返す
if (deg >= 4) return mx + 1;
if (deg == 3) return 1; // 次数が 3 のときは now が終点になる
return 0;
};
dfs(dfs, 0);
cout << ans << endl;
};
int q;
cin >> q;
rep(i, q) cal();
}