皆様こんにちは！ばるとーくです！
今回はABC473の振り返りをしていこうと思います！
はじめに ～結果～
今回は3完となりました！
とはいえF問題に手がかかりそうなのやばい...
（いくらライブラリゲーだったとはいえすごいことだと思いますマジで）
各問題振り返り
A - Second Half Sum
問題文
長さ $N$ の整数列 $A=(A_1,A_2,\dots,A_N)$ が与えられます。ここで、 $N$ は偶数です。 $A$ の後半部分の総和、つまり、 $A_{(N/2)+1},A_{(N/2)+2},\dots,A_{N}$ の総和を求めてください。
制約
- 入力は全て整数
- $N$ は $2 \le N \le 100$ を満たす偶数
- $1 \le A_i \le 100$
A - Second Half Sum
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoder
特にいうことはないですね．
愚直に全部足して求めました．
（いや本当に言うことがない...）
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
int main() {
int n;
cin >> n;
int ans = 0;
rep(i, 0, n) {
int inp;
cin >> inp;
if (i + 1 > n / 2) {
ans += inp;
}
}
cout << ans << "\n";
return 0;
}
B - Old Maid
問題文
高橋くんは、現在 $N$ 枚のカードを持っています。 $i$ 番目 $(1\le i\le N)$ のカードには整数 $A _ i$ が書かれています。
高橋くんは、以下の操作を可能な限り繰り返します。
- 同じ整数が書かれている異なる 2 枚のカードを選び、それら 2 枚のカードを食べる。食べたカードは永久に取り除かれ、以降の操作で選ぶことはできない。
操作ができなくなったときに残っているカードに書かれている整数の合計を求めてください。
制約
- $1\le N\le100$
- $1\le A _ i\le100\ (1\le i\le N)$
- 入力はすべて整数
B - Old Maid
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoder
いきなりカードを食べだす高橋君につい笑ってしまうばるとーくさんでありました．
解き方としては，全探索を行います．
バブルソートの実装でよく見るような，きれいな $O(n^2)$ 解法です．
ポイントは，食べたカードは $0$ にすることでしょうか．残ったカードに書かれた整数の合計を聞かれているので，$0$ にしておけばif文で条件分岐をしなくてもただすべてを足すだけでもとまるので楽でした～
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
int main() {
int n;
cin >> n;
vector<int> a(n);
rep(i, 0, n) {
cin >> a[i];
}
rep(i, 0, n) {
if (a[i] == 0) {
continue;
}
rep(j, i + 1, n) {
if (a[i] == a[j]) {
a[i] = 0;
a[j] = 0;
break;
}
}
}
int ans = 0;
rep(i, 0, n) {
ans += a[i];
}
cout << ans << "\n";
return 0;
}
C - Change Schools
問題文
現在 AtCoder 高校には $K$ 個のクラスと $N$ 人の生徒が存在し、$i$ 人目 $(1\le i\le N)$ の生徒は $A _ i$ 番目のクラスに所属しています。
高橋くんは $9$ 月から AtCoder 高校に転入することになりました。 高橋くんは、転入する際に $K$ 個のクラスの中から好きなクラスを $1$ つ選び、そのクラスに所属することができます。
高橋くんは、自分が所属しているクラスより多い人数が所属しているクラスがあるとき悲しみ、そうでないとき喜びます。
所属したときに高橋くんが喜ぶクラスがいくつあるか求めてください。
制約
- $1\le N\le2\times10 ^ 5$
- $1\le K\le N$
- $1\le A _ i\le K\ (1\le i\le N)$
- 入力はすべて整数
C - Change Schools
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoder
高橋君が喜ぶ条件が，「高橋君を除いて最も人数の多いクラスか，それより $1$ 人少ないクラスに属する」ことだけだと気づいたので，
- 各クラスの生徒の人数を調べる
- それを降順ソートする
- 先頭に来たクラスは最多人数であるので，それより $2$ 人以上少ないクラスが出てくるまで数える
数え終わったら，これが答えになりました．
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
int main() {
int n, k;
cin >> n >> k;
vector<int> cl(k);
rep(i, 0, n) {
int inp;
cin >> inp;
++cl[--inp];
}
sort(cl.rbegin(), cl.rend());
ll ans = 1;
int maxk = cl[0];
rep(i, 1, k){
if(cl[i] < maxk - 1){
break;
}
++ans;
}
cout << ans << "\n";
return 0;
}
F - A/AB Insertion
問題文
長さ $N$ の A, B からなる文字列 $S$ が与えられます。 以下のクエリを合計 $Q$ 個処理してください。
タイプ $1$ : $S$ の $i$ 文字目を $c$ に変更する。
タイプ $2$ : 文字列 $T$ を、現在の文字列 $S$ の $l$ 文字目から $r$ 文字目までを抜き出した文字列とする。 文字列 $T$ が以下の操作で得られる文字列であれば Yes 、そうでなければ No と出力する。
- 空文字列から始め、以下の $2$ つの操作を好きな順序で $0$ 回以上何回でも行う。
- 文字列の(先頭・末尾を含めた)任意の箇所を選択し、そこに A を挿入する。
- 文字列の(先頭・末尾を含めた)任意の箇所を選択し、そこに AB を挿入する。
制約
- $N$ は $1 \le N \le 5 \times 10^5$ を満たす整数
- $S$ は A, B からなる長さ $N$ の文字列
- $Q$ は $1 \le Q \le 2 \times 10^5$ を満たす整数
- 与えられるクエリはタイプ $1,2$ のいずれかである
- タイプ $1$ のクエリは以下の制約を満たす $i$ は $1 \le i \le N$ を満たす整数 $c$ は A, B のいずれか
- $i$ は $1 \le i \le N$ を満たす整数
- $c$ は A, B のいずれか
- タイプ $2$ のクエリは以下の制約を満たす $l,r$ は $1 \le l \le r \le N$ を満たす整数
- $l,r$ は $1 \le l \le r \le N$ を満たす整数
F - A/AB Insertion
AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.
AtCoder
「D, Eすっ飛ばしていきなりFなんか?」とお思いでしょうが，これセグメントツリーなんですよ．
これに気づいた私，「行ける！」と確信して組み立て始めました．
文字列だと厄介なので，「文字列 $T$ の中で，(Aの個数) < (Bの個数) となったら絶対に作れないな」と考え，Aに変更するときは $1$ に，Bに変更するときは $-1$ に，というような操作を行いました．
あとはその和を計算して，0以上になったら Yes, そうでなければ No とすればいいじゃん！と考え，以下のコードを書きました．
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
struct SegmentTree {
int n;
vector<ll> tree;
ll unit; // 単位元（初期値）
function<ll(ll, ll)> op; // 演算（min, max, sumなど）
// コンストラクタ: サイズ、初期値、演算を指定
SegmentTree(int _n, ll _unit, function<ll(ll, ll)> _op)
: unit(_unit), op(_op) {
n = 1;
while (n < _n) n <<= 1;
tree.assign(n * 2, unit);
}
// 値の更新: i番目をxに変更
void update(int i, ll x) {
i += n;
tree[i] = x;
while (i > 1) {
i >>= 1;
tree[i] = op(tree[i << 1], tree[i << 1 | 1]);
}
}
void build(const vector<ll>& v) {
for (int i = 0; i < (int)v.size(); i++) {
tree[n + i] = v[i];
}
// 下の段から順番に親を計算していく
for (int i = n - 1; i >= 1; i--) {
tree[i] = op(tree[i << 1], tree[i << 1 | 1]);
}
}
// 区間クエリ: [l, r) の範囲を計算（半開区間）
ll query(int l, int r) {
ll res_l = unit;
ll res_r = unit;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res_l = op(res_l, tree[l++]);
if (r & 1) res_r = op(tree[--r], res_r);
}
return op(res_l, res_r);
}
};
// how to use
/*
// 最小値を求めたいとき（単位元は「十分大きい値」）
SegmentTree st_min(n, LLONG_MAX, [](ll a, ll b){ return min(a, b); });
// 最大値を求めたいとき（単位元は「十分小さい値」）
SegmentTree st_max(n, LLONG_MIN, [](ll a, ll b){ return max(a, b); });
// 和を求めたいとき（単位元は「0」）
SegmentTree st_sum(n, 0, [](ll a, ll b){ return a + b; });
// 3番目の要素（0-indexed）を 100 に変更
st_min.update(3, 100);
// 2番目から 5番目まで（[2, 6)）の最小値をゲット※半開区間
ll result = st_min.query(2, 6);
*/
int main() {
int n;
cin >> n;
string s;
cin >> s;
int q;
cin >> q;
SegmentTree moji(n, 0, [](ll a, ll b) { return a + b; });
rep(i, 0, n){
if(s[i] == 'A'){
moji.update(i, 1);
}else{
moji.update(i, -1);
}
}
rep(i, 0 ,q){
int type;
cin >> type;
if(type == 1){
cerr << 1 << " ";
int a;
char b;
cin >> a >> b;
--a;
cerr <<"\n";
if(b == 'A'){
moji.update(a, 1);
}else{
moji.update(a, -1);
}
}else if(type == 2){
cerr << 2 << " ";
int l, r;
cin >> l >> r;
ll result = moji.query(l - 1, r);
cerr << result << "\n";
if(result >= 0){
cout << "Yes" << "\n";
}else{
cout << "No" << "\n";
}
}
}
return 0;
}
しかし結果はWA，不正解でしたとさ．
原因が見つからず，残念ながら時間切れに...
あとからClaudeとともに解明した結果．「足している最中に一度でも合計が負になったら(Bのみを挿入する術はないので)作れない」という条件を見落としていることがわかり，絶望しました...
いくらF問題といえ，解けたよこれ...
修正したコードがこれです．モノイドに対する理解の重要性を考えさせられましたね...
cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for (ll i = a; i < b; ++i)
#define rrep(i, a, b) for (ll i = a; i >= b; --i)
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
struct S {
ll sum, mn;
};
const ll INF = 1e18;
struct SegmentTree {
int n;
vector<S> tree;
S unit; // 単位元（初期値）
function<S(S, S)> op; // 演算（min, max, sumなど）
// コンストラクタ: サイズ、初期値、演算を指定
SegmentTree(int _n, S _unit, function<S(S, S)> _op)
: unit(_unit), op(_op) {
n = 1;
while (n < _n) n <<= 1;
tree.assign(n * 2, unit);
}
// 値の更新: i番目をxに変更
void update(int i, S x) {
i += n;
tree[i] = x;
while (i > 1) {
i >>= 1;
tree[i] = op(tree[i << 1], tree[i << 1 | 1]);
}
}
void build(const vector<S>& v) {
for (int i = 0; i < (int)v.size(); i++) {
tree[n + i] = v[i];
}
// 下の段から順番に親を計算していく
for (int i = n - 1; i >= 1; i--) {
tree[i] = op(tree[i << 1], tree[i << 1 | 1]);
}
}
// 区間クエリ: [l, r) の範囲を計算（半開区間）
S query(int l, int r) {
S res_l = unit;
S res_r = unit;
for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
if (l & 1) res_l = op(res_l, tree[l++]);
if (r & 1) res_r = op(tree[--r], res_r);
}
return op(res_l, res_r);
}
};
// how to use
/*
// 最小値を求めたいとき（単位元は「十分大きい値」）
SegmentTree st_min(n, LLONG_MAX, [](ll a, ll b){ return min(a, b); });
// 最大値を求めたいとき（単位元は「十分小さい値」）
SegmentTree st_max(n, LLONG_MIN, [](ll a, ll b){ return max(a, b); });
// 和を求めたいとき（単位元は「0」）
SegmentTree st_sum(n, 0, [](ll a, ll b){ return a + b; });
// 3番目の要素（0-indexed）を 100 に変更
st_min.update(3, 100);
// 2番目から 5番目まで（[2, 6)）の最小値をゲット※半開区間
ll result = st_min.query(2, 6);
*/
int main() {
int n;
cin >> n;
string s;
cin >> s;
int q;
cin >> q;
// 構築
SegmentTree moji(n, S{0, INF},
[](S a, S b) { return S{a.sum + b.sum, min(a.mn, a.sum + b.mn)}; });
// 葉（初期化・更新とも）
// 判定
rep(i, 0, n) {
if (s[i] == 'A') {
moji.update(i, S{1, 1});
} else {
moji.update(i, S{-1, -1});
}
}
rep(i, 0, q) {
int type;
cin >> type;
if (type == 1) {
int a;
char b;
cin >> a >> b;
--a;
s[a] = b;
if (b == 'A') {
moji.update(a, S{1, 1});
} else {
moji.update(a, S{-1, -1});
}
} else if (type == 2) {
int l, r;
cin >> l >> r;
S result = moji.query(l - 1, r);
cout << (result.mn >= 0 ? "Yes" : "No") << "\n";
}
}
return 0;
}
最後に～レート変化～
パフォーマンスは前回よりだいぶ落としたとはいえ，順調ですね！
さあ，入茶はいつになるでしょね？
最後までお読みいただきありがとうございました！
時間がある方は，おすすめ欄よりぜひほかの記事ものぞいて行ってくださいね！
また，作品集のページ・リンク集ものぞいてみてくださいね！
それでは，またお会いしましょう！
コメント