ABC 444
Table of Contents
https://atcoder.jp/contests/abc444
A. Repdigit
https://atcoder.jp/contests/abc444/tasks/abc444_a
2026/2/7 コンテスト中に自力 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
string N;
cin >> N;
yesno(N[0] == N[1] && N[1] == N[2]);
}
B. Digit Sum
https://atcoder.jp/contests/abc444/tasks/abc444_b
2026/2/7 コンテスト中に自力 AC
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, K;
cin >> N >> K;
auto f = [](ll x) -> ll {
ll ret = 0;
while (x) {
ret += x % 10;
x /= 10;
}
return ret;
};
ll ans = 0;
rep2(i, 1, N + 1) {
if (f(i) == K) ans++;
}
cout << ans << endl;
}
C. AtCoder Riko
https://atcoder.jp/contests/abc444/tasks/abc444_c
2026/2/7 コンテスト中に自力 AC
$L$ の候補としては $A$ の最大値か $\max A_i + \min A_i$ のどちらかだろうとなんとなく想像できたが確証なく提出した。
解説
$A$ をソートしておいても問題に影響はないので昇順にソートしておく。
折れていないものがある場合は $A$ に含まれる最大値が $L$ であるので $L = A_N$ として実現可能かチェックする。
すべての AtCoder りこが折れている場合。$A_N$ とペアになるのは $A_1 \sim A_{N-1}$ のいずれかであるので $L$ の下限は $A_1 + A_N$となる。よって $A_1 + A_L \leq L$。 逆に $A_1$ とペアになるのは $A_2 \sim A_N$ のいずれかであるので $L$ の上限は $A_1 + A_L$。 よって $A_1 + A_N \leq L$。 以上より $L = A_1 + A_L$ となるのでこれを実現可能かチェックする。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
vll A(N);
rep(i, N) cin >> A[i];
sort(all(A));
map<ll, ll> mp;
for (ll a : A) mp[a]++;
auto check = [&](ll x) -> bool {
int ok = 1;
for (auto [key1, num1] : mp) {
if (x == key1) continue;
ll key2 = abs(x - key1);
ll num2 = mp[key2];
if (key1 == key2 && num1 % 2 == 1) { // 同じ長さに折れた場合、その長さの本数が偶数でないとペアが作れない
ok = 0;
}
if (key1 != key2 && num1 != num2) {
ok = 0;
}
}
return ok;
};
set<ll> ans;
// max に揃える
if (check(A.back())) ans.insert(A.back());
ll x = A[0] + A.back(); // min と max に揃える
if (check(x)) ans.insert(x);
vll v;
for (auto a : ans) v.push_back(a);
print(v);
}
D. Many Repunit Sum
https://atcoder.jp/contests/abc444/tasks/abc444_d
2026/2/7 コンテスト中に自力 AC
各桁に 1 がいくつあるかをいもす法で求めて、繰り上がりを処理する。
コンテスト中は $2 \times 10^5$ 桁の数が $2 \times 10^5$ 個足したとき桁数が最大でいくつになるのか見積もり混乱して $2 \times 10^7$ まで確保したが $(2 \times 10^5 \text{桁の数}) \times (2 \times10^5)$ だからせいぜい５桁くらい増えるだけだった。
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
vll A(N);
rep(i, N) cin >> A[i];
ll m = 2e5 + 10;
vll digit(m);
for (ll a : A) {
digit[0]++;
digit[a]--;
}
rep2(i, 1, m) digit[i] += digit[i - 1];
rep(i, m - 1) {
ll r = digit[i] % 10;
ll q = digit[i] / 10;
digit[i] = r;
digit[i + 1] += q;
}
while (digit.back() == 0) digit.pop_back();
reverse(all(digit));
for (ll a : digit) cout << a;
cout << endl;
}
無駄なメモリを消費しない代わりに $O(N \log N)$ で解く方法
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N;
cin >> N;
vll A(N);
rep(i, N) cin >> A[i];
sort(all(A));
ll d = 1;
ll inc = 0;
vll ans;
while (true) {
auto it = lower_bound(all(A), d);
ll x = inc + (A.end() - it);
if (x == 0) break;
ans.push_back(x % 10);
inc = x / 10;
d++;
}
reverse(all(ans));
for (ll x : ans) cout << x;
cout << endl;
}
E. Sparse Range
https://atcoder.jp/contests/abc444/tasks/abc444_e
2026/2/7 コンテスト中に自力 AC
$S$ をどの要素の差も $D$ 以上である集合とする。 はじめ $S$ は空集合である。
$l = r = 1$ として尺取法で $r$ を $1$ から $N$ まで動かす。
- $A_r$ を $S$ に追加しても、どの要素の差も $D$ 以上であるならば、そのまま $S$ に追加する
- 答えに $|S|$ を加える
- 右端を $r$ に固定したときに選べる $l$ の個数が集合の大きさに等しいため
- ちなみに $|S| = r - l + 1$ である
- 答えに $|S|$ を加える
- $A_r$ を $S$ に追加したとき、ある要素 $x$ との間の差が $D$ 未満になるならば、その $x$ がなくなるまで $S$ から要素 $A_l, A_{l+1}, \cdots, A_{l+k} = x$ を削除し、$l$ を $l+k+1$ に更新する
- その後 $A_r$ を $S$ に追加する
- 答えに $|S|$ を加える
void solve() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll N, D;
cin >> N >> D;
vll A(N);
rep(i, N) cin >> A[i];
// number, index
map<ll, ll> S;
S[-INF] = S[INF] = -1; // sentinel
int l = 0;
auto del_neigh = [&](ll x) -> void {
ll tmpl = -1;
auto it = S.lower_bound(x);
auto [num1, index1] = *it;
if (abs(num1 - x) < D) chmax(tmpl, index1);
it--;
auto [num2, index2] = *it;
if (abs(num2 - x) < D) chmax(tmpl, index2);
while (l <= tmpl) {
S.erase(A[l]);
l++;
}
};
ll ans = 0;
rep(r, N) {
del_neigh(A[r]);
S[A[r]] = r;
ans += r - l + 1;
}
cout << ans << endl;
}
F. Half and Median
https://atcoder.jp/contests/abc444/tasks/abc444_f