ABC 442
Table of Contents
https://atcoder.jp/contests/abc442
A. Count
https://atcoder.jp/contests/abc442/tasks/abc442_a
2026/1/24 コンテスト中に自力 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
ll ans = 0;
for (char c : s) {
if (c == 'i' || c == 'j') ans++;
}
cout << ans << endl;
}
B. Music Player
https://atcoder.jp/contests/abc442/tasks/abc442_b
2026/1/24 コンテスト中に自力 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int Q;
cin >> Q;
ll vol = 0, on = 0;
rep(i, Q) {
ll a;
cin >> a;
if (a == 1) {
vol++;
} else if (a == 2) {
vol = max(0ll, vol - 1);
} else {
on = 1 - on;
}
yesno(vol >= 3 && on);
}
}
C. Peer Review
https://atcoder.jp/contests/abc442/tasks/abc442_c
2026/1/24 コンテスト中に自力 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, M;
cin >> N >> M;
vll rigai(N);
rep(i, M) {
ll a, b;
cin >> a >> b;
a--, b--;
rigai[a]++;
rigai[b]++;
}
vll ans;
rep(i, N) {
ll x = rigai[i];
ll c = N - x - 1;
ans.push_back(c * (c - 1) * (c - 2) / 6);
}
print(ans);
}
D. Swap and Range Sum
https://atcoder.jp/contests/abc442/tasks/abc442_d
2026/1/24 コンテスト中に自力 AC
1点更新、区間和の segment tree まんまだったのでそれで実装した。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, Q;
cin >> N >> Q;
vll A(N);
rep(i, N) cin >> A[i];
auto op = [](ll a, ll b) -> ll {
return a + b;
};
auto e = []() -> ll {
return 0;
};
segtree<ll, op, e> seg(A);
while (Q--) {
int t;
cin >> t;
if (t == 1) {
ll x;
cin >> x;
x--;
ll l = seg.get(x), r = seg.get(x + 1);
seg.set(x, r);
seg.set(x + 1, l);
} else {
ll l, r;
cin >> l >> r;
l--;
cout << seg.prod(l, r) << endl;
}
}
}
2026/1/25 コンテスト後に解いた累積和での別解
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, Q;
cin >> N >> Q;
vll A(N);
rep(i, N) cin >> A[i];
vll cm(N + 1);
rep(i, N) cm[i + 1] = cm[i] + A[i];
while (Q--) {
int t;
cin >> t;
if (t == 1) {
ll x;
cin >> x;
x--;
swap(A[x], A[x + 1]);
cm[x + 1] = cm[x] + A[x];
cm[x + 2] = cm[x + 1] + A[x + 1];
} else {
ll l, r;
cin >> l >> r;
l--;
cout << cm[r] - cm[l] << '\n';
}
}
}
E. Laser Takahashi
https://atcoder.jp/contests/abc442/tasks/abc442_e
2026/1/24 コンテスト中に自力 AC
まずモンスターを並び替える。 時計回りで並べたいので第1象限、第4象限、第3象限、第2象限の順に並べる。 各象限内では傾きが大きい順に並べる。
$(x_i, y_i)$ と $(x_j, y_j)$ の傾きを比較するには
\begin{align*} \frac{y_i}{x_i} > \frac{y_j}{x_j} \iff y_i \cdot x_j > x_i \cdot y_j \end{align*}
をもとに比較すれば良い。
各クエリでは $(x_a, y_a)$ と $(x_b, y_b)$ の間にいるモンスターの数を数える。
並び替えたモンスター列に対して $(x_a, y_a)$ の傾きの下限を $l$, $(x_b, y_b)$ の傾きの上限を $r$ としたとき、 $l < r$ ならば $r - l$ が答え。 $r <= l$ ならば $N - l + r$ が答え。
コンテスト中は同じ傾き同士のものをグルーピングしたり、gcd で x,y を割ったりしたが不要だった。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, Q;
cin >> N >> Q;
vll X(N), Y(N);
rep(i, N) cin >> X[i] >> Y[i];
auto area_id = [](ll x, ll y) -> ll {
if (x >= 0 && y >= 0) return 0;
if (x >= 0 && y < 0) return 1;
if (x < 0 && y <= 0) return 2;
// x < 0 && y > 0
return 3;
};
// x, y
using P = tuple<ll, ll>;
vector<P> monsters;
rep(i, N) monsters.emplace_back(X[i], Y[i]);
auto less = [&](const P& a, const P& b) -> bool {
auto [xi, yi] = a;
auto [xj, yj] = b;
ll ida = area_id(xi, yi), idb = area_id(xj, yj);
if (ida != idb) return ida < idb;
return yi * xj > xi * yj;
};
sort(all(monsters), less);
while (Q--) {
ll a, b;
cin >> a >> b;
a--, b--;
ll xi = X[a], yi = Y[a];
ll xj = X[b], yj = Y[b];
P pi = {xi, yi};
P pj = {xj, yj};
auto lid = lower_bound(all(monsters), pi, less) - monsters.begin();
auto rid = upper_bound(all(monsters), pj, less) - monsters.begin();
ll ans = 0;
if (lid < rid) {
ans = rid - lid;
} else {
ll tl = N - lid;
ll rl = rid;
ans = tl + rl;
}
cout << ans << endl;
}
}
F. Diagonal Separation 2
https://atcoder.jp/contests/abc442/tasks/abc442_f
2026/1/25 コンテスト後に解いた自力 AC
任意の白マスについて問題の条件よりそのマスよりも上のあるマスはすべて白マスであり、またそのマスよりも左のあるマスもすべて白マスである。 よって黒は階段状に並んでいることになる。
処理を簡単にするためにすべての行の先頭に . を追加して、幅を1増やしておく。
$dp_{i,j}$ を $i$ 行目の $j$ 番目までを白、$j+1$ 番目以降を黒にしたときの最小コストとし、 $B_{i,j}$ を $i$ 行目の $j$ 番目までの黒マスの数、$W_{i,j}$ を $i$ 行目の $j$ 番目までの白マスの数とする。
遷移は以下のようになる。
\begin{align*} dp_{i,j} = B_{i,j} + (W_{i,N} - W_{i,j}) + \min_{k \in [j,N]} dp_{i-1,k} \end{align*}
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
vector<string> grid(N);
rep(i, N) {
cin >> grid[i];
grid[i] = "." + grid[i];
}
ll H = N, W = N + 1;
vll dp(W);
rep(i, H) {
vll dpn(W, INF);
vll cmb(W + 1), cmw(W + 1);
rep(j, W) {
cmb[j + 1] = cmb[j] + (grid[i][j] == '#');
cmw[j + 1] = cmw[j] + (grid[i][j] == '.');
}
vll mi = dp;
for (int j = W - 2; j >= 0; j--) {
chmin(mi[j], mi[j + 1]);
}
for (int j = W - 1; j >= 0; j--) {
ll nw = cmw[W] - cmw[j + 1];
ll nb = cmb[j + 1];
chmin(dpn[j], mi[j] + nb + nw);
}
swap(dp, dpn);
}
ll ans = *min_element(all(dp));
cout << ans << endl;
}