ABC 334
Table of Contents
https://atcoder.jp/contests/abc334
A. Christmas Present
https://atcoder.jp/contests/abc334/tasks/abc334_a
B. Christmas Trees
https://atcoder.jp/contests/abc334/tasks/abc334_b
C. Socks 2
https://atcoder.jp/contests/abc334/tasks/abc334_c
2026/1/18 自力 AC
ペアが作れる靴下はペアを作って問題ない。
三角不等式 $|a + b| \leq |a| + |b|$ より
\begin{align} |A_i - A_j| &= |(A_i - A_p) - (A_j - A_p)| \\ &\leq |A_i - A_p| + |-(A_j - A_p)| \\ &= |A_i - A_p| + |A_j - A_p| \end{align}
であるから、$A_p$ がペアを作れる場合、下手に $A_p$ を $A_i$ や $A_j$ をペアにするよりも、$A_i$ と $A_j$ をペアにした方が差が小さくなる、または変わらない。よって、ペアを作れる靴下は全てペアを作って良い。
K が偶数の場合
愚直に $(A_1, A_2), \cdots (A_{K-1}, A_K)$ でペアを作れば良い。
証明
$B_1 < B_2 < B_3 < B_4$ とする。 このとき
\begin{align} |B_1 - B_2| + |B_3 - B_4| &= (B_2 - B_1) + (B_4 - B_3) \\ &= (B_4 - B_1) - (B_3 - B_2) \\ &\leq (B_4 - B_1) + (B_3 - B_2) \\ &= |B_1 - B_4| + |B_2 - B_3| \\ \end{align}
\begin{align} |B_1 - B_2| + |B_3 - B_4| &= (B_2 - B_1) + (B_4 - B_3) \\ &= (B_4 - B_1) - (B_3 - B_2) \\ &\leq (B_4 - B_1) + (B_3 - B_2) \\ &= (B_3 - B_1) + (B_4 - B_2)\\ &= |B_1 - B_3| + |B_2 - B_4| \\ \end{align}
であるので、隣接する要素でペアを作るのが最適である。
K が奇数の場合
ref: https://atcoder.jp/contests/abc334/editorial/8983
$i$ 番目の要素を使わないとしたときの奇妙さを $S_i$ とすると $S_i$ の最小値が答えとなる。
(0-index) で $S_0$ をまず求める。
- $S_1$ は $S_0$ から $-(A_2 - A_1) + (A_2 - A_0)$ を足したものである。
- $S_2$ は $S_1$ から $-(A_2 - A_0) + (A_1 - A_0)$ を足したものである。
一般に
- $i$ が奇数のとき $S_i = S_{i-1} - (A_{i+1} - A_i) + (A_{i+1} - A_{i-1})$
- $i$ が偶数のとき $S_i = S_{i-1} - (A_i - A_{i-2}) + (A_{i-1} - A_{i-2})$
である。
以上よりこの問題は $O(K)$ で解ける
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, K;
cin >> N >> K;
vll A(K);
rep(i, K) cin >> A[i];
if (K % 2 == 0) {
ll ans = 0;
for (int i = 0; i < K; i += 2) ans += A[i + 1] - A[i];
cout << ans << endl;
return;
}
ll sum = 0;
for (int i = 1; i < K; i += 2) {
sum += A[i + 1] - A[i];
}
ll ans = sum;
rep2(i, 1, K) {
if (i % 2 == 1) {
sum -= A[i + 1] - A[i];
sum += A[i + 1] - A[i - 1];
} else {
sum -= A[i] - A[i - 2];
sum += A[i - 1] - A[i - 2];
}
chmin(ans, sum);
}
cout << ans << endl;
}
D. Reindeer and Sleigh
https://atcoder.jp/contests/abc334/tasks/abc334_d
2026/1/18 自力 AC
$R$ を昇順にソートし、累積和を計算して $X$ について二分探索すれば良い。segment tree を用いると実装が楽。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, Q;
cin >> N >> Q;
vll R(N);
rep(i, N) cin >> R[i];
sort(all(R));
auto op = [](ll a, ll b) -> ll {
return a + b;
};
auto e = []() -> ll {
return 0;
};
segtree<ll, op, e> seg(R);
rep(i, Q) {
ll X;
cin >> X;
auto f = [&](ll x) -> bool {
return x <= X;
};
ll ans = seg.max_right(0, f);
cout << ans << endl;
}
}
E. Christmas Color Grid 1
https://atcoder.jp/contests/abc334/tasks/abc334_e
2026/1/18 自力 AC
緑の連結成分は union find で管理する。
緑の連結成分の個数を $G$ とする。赤のマスに隣接する緑の連結成分の個数を $k$ とすると、その赤のマスが緑に変わるとき、緑の連結成分の個数は $G - (k - 1)$ になる。 赤マスに隣接する緑の連結成分がない場合、その赤マスは新たな緑の連結成分になるので、緑の連結成分の個数は $G + 1$ になる。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll H, W;
cin >> H >> W;
vector<string> grid(H);
rep(i, H) cin >> grid[i];
dsu uf(H * W);
vint di = {0, 1, 0, -1};
vint dj = {1, 0, -1, 0};
ll numr = 0;
rep(i, H) rep(j, W) {
if (grid[i][j] == '.') {
numr++;
continue;
}
rep(d, 4) {
ll ni = i + di[d], nj = j + dj[d];
if (clamp(ni, 0ll, H - 1) != ni || clamp(nj, 0ll, W - 1) != nj) continue;
if (grid[ni][nj] == '#')
uf.merge(i * W + j, ni * W + nj);
}
}
mint ans = 0;
mint ngreen = 0;
{
set<int> s;
rep(i, H) rep(j, W) {
if (grid[i][j] == '.') continue;
s.insert(uf.leader(i * W + j));
}
ngreen = s.size();
}
rep(i, H) rep(j, W) {
if (grid[i][j] == '#') continue;
set<ll> neigh;
rep(d, 4) {
ll ni = i + di[d], nj = j + dj[d];
if (clamp(ni, 0ll, H - 1) != ni || clamp(nj, 0ll, W - 1) != nj) continue;
if (grid[ni][nj] == '#')
neigh.insert(uf.leader(ni * W + nj));
}
ans += ngreen;
if (neigh.size()) {
ans -= (ll)neigh.size() - 1;
} else {
ans++;
}
}
ans /= numr;
cout << ans.val() << endl;
}
F. Christmas Present 2
https://atcoder.jp/contests/abc334/tasks/abc334_f