はじめに
みなさま、どうもこんにちは！
毎度おなじみばるとーくでござります…
というわけで、ABC455の振り返りをやっていきます。
結論から言うと、AとCの2完でした…
あの…グリッドが苦手すぎて草も生えんですわ。
C問題はよく頑張った。まじで。時間かかりすぎだけど。
あとD問題は計算量の壁ががが…
振り返り
A - 455
問題文
整数
A,B,Cが与えられます。A=BかつB=CであるならばYesを、そうでないならばNoを出力してください。制約
1≤A,B,C≤9- 入力される値はすべて整数
講評
これに対してのコードはこんな感じ
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
int main() {
int a, b, c;
cin >> a >> b >> c;
if (a != b && b == c) {
cout << "Yes" << "\n";
} else {
cout << "No" << "\n";
}
return 0;
}
うん、特に問題ないと思います。
ただ提出に2分かかったの地味に痛いかもね？
言い訳すると、前回のあれがトラウマで…
B - Spiral Galaxy
問題文
H行W列のグリッドがあります。このグリッドの上からi行目、左からj列目のマスをマス(i,j)と表記します。グリッドの各マスは白または黒で塗られています。グリッドの情報は
H個の長さWの文字列S1,S2,…,SHによって与えられ、Siのj文字目が.のときマス(i,j)は白で、Siのj文字目が#のときマス(i,j)は黒で塗られています。グリッドの長方形領域であって、点対称に塗られているものの個数を求めてください。
より形式的には、以下の条件をすべて満たす整数の組
(h1,h2,w1,w2)の個数を求めてください。
1≤h1≤h2≤H1≤w1≤w2≤Wh1≤i≤h2かつw1≤j≤w2を満たすすべての整数i,jについてマス(i,j)とマス(h1+h2−i,w1+w2−j)は同じ色で塗られている制約
1≤H,W≤10H,Wは整数Siは.,#からなる長さWの文字列
講評
なんとこちら、ばるとーくさんパスを選択しております！
AtCoder Sempaiにもこっぴどく叱られております！！
だって…苦手なんだものグリッドぉ～
テンプレを頑張って作ろうってことやな。うん。
それにしても6重ループはやばすぎる。わかってても組めてない自信あり（実装力 is どこ？）
C - Vanish
問題文
整数列
A=(A1,A2,…,AN)が与えられます。以下の操作をちょうど
K回行った後のAの各要素の和として考えられる最小値を求めてください。
- 整数
xを選ぶ。Ai=xなる各iについてAiの値を0に置き換える。制約
1≤K≤N≤3×1051≤Ai≤109- 入力される値はすべて整数
講評
こんなコードを書きました
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// --- 初期設定（入出力の高速化と小数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<ll> A(n);
ll sum = 0;
for (int i = 0; i < n; i++) {
cin >> A<!--SC_0-->;
sum += A<!--SC_1-->;
}
sort(A.begin(), A.end());
vector<pair<ll, int>> mem(1);
ll m = 0;
int num = 0;
for (int i = 0; i < n; i++) {
if (A<!--SC_2--> != m) {
mem.push_back(make_pair(m, num));
mem.resize(mem.size() + 1);
m = A<!--SC_3-->;
num = 1;
} else {
++num;
}
}
mem.push_back(make_pair(m, num));
vector<ll> sub(1);
for (int i = 0; i < mem.size(); i++) {
sub.push_back(mem<!--SC_4-->.first * mem<!--SC_5-->.second);
sub.resize(sub.size() + 1);
cerr << mem<!--SC_6-->.first << mem<!--SC_7-->.second << endl;
}
sort(sub.rbegin(), sub.rend());
for (int i = 0; i < k; i++) {
if (i > sub.size()) {
break;
}
sum -= sub<!--SC_8-->;
cerr << sum << endl;
}
if (sum < 0) {
sum = 0;
}
cout << sum << endl;
return 0;
}
まず、「（x * 出現回数）の値が最も大きくなるxから0にすればいい」ということは簡単に思いつきました。
そこから、なんすよねぇ～
まずkの存在を見落としていたり、mapがうまく使えなかったりして、結局こうなりましたとさ。
さっさと入茶したかったらここまで30分もかからず解けたほうがいいんだろうな
あと、push_backとresizeを多用しすぎなんじゃないかな～と
実際デバック大変だったよこれ。
D - Card Pile Query
問題文
カードが
N枚とカードの山がN個あります。カードとカードの山にはそれぞれ
1,2,…,Nの番号が付けられており、はじめ、山iにはカードiのみが積まれています。あなたは、各
i=1,2,…,Qに対して以下の操作をこの順に行います。
- カード
CiおよびカードCiの上に積まれているカードを順序を保ってカードPiの上に移動させる。ただし、操作を行う直前の時点でカードCiとカードPiは異なる山にあり、カードPiはある山の一番上に積まれていることが保証される。すべての操作を終えた後、各山に積まれているカードの枚数を求めてください。
制約
1≤N,Q≤3×1051≤Ci,Pi≤N- 操作を順に行ったとき、各操作を行う直前の時点でカード
CiとカードPiは異なる山にある- 操作を順に行ったとき、各操作を行う直前の時点でカード
Piはある山の一番上に積まれている- 入力される値はすべて整数
講評
こんなコードを書きました
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// --- 初期設定（入出力の高速化と小数15桁出力） ---
struct Init {
Init() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout << fixed << setprecision(15);
}
} init;
// ------------------------------------------------
int main() {
int n, q;
cin >> n >> q;
vector<stack<int>> st(n);
vector<int> where(n);
for (int i = 0; i < n; i++) {
st<!--SC_9-->.push(i);
where<!--SC_10--> = i;
}
for (int i = 0; i < q; i++) {
int c, p;
cin >> c >> p;
--c; // 0-indexed
--p;
int move = where<!--SC_11-->;
stack<int> tmp;
while (st<!--SC_12-->.top() != c) {//抜く
tmp.push(st<!--SC_13-->.top());
where[tmp.top()] = p;
st<!--SC_14-->.pop();
cerr << move << st<!--SC_15-->.size() << endl;
}
tmp.push(st<!--SC_16-->.top());
where[tmp.top()] = where<!--SC_17-->;
st<!--SC_18-->.pop();
cerr << move << st<!--SC_19-->.size() << endl;
while (tmp.size() != 0) {//足す
st[where<!--SC_20-->].push(tmp.top());
tmp.pop();
cerr << p << st[where<!--SC_21-->].size() << endl;
}
}
for (int i = 0; i < n; i++) {
cout << st<!--SC_22-->.size() << " ";
}
cout << "\n";
return 0;
}
REです。
Claude曰くこうらしいです。
where<!--SC_23-->は「カードiがどの山にあるか」を表す配列。 移動先は「カードpのいる山」、つまりwhere<!--SC_24-->です。 ところが上のコードではwhere[tmp.top()] = pと、カード番号pを山番号として代入しています（その下ではwhere[tmp.top()] = where<!--SC_25-->と正しく書かれているのに）。
これによりwhere[]が壊れ、後続のクエリで存在しない山にアクセスしようとしてREします。
あと、しんぷるにこれだとO(NQ)なのでTLEしちゃうんですよね…
解説聞いて、Claudeと一緒に紐解いたらやっとうなずけました。貴様連結リストかぁ。
おわりに
今日のABCにより、始めてから半年以内に入茶するという目標は潰えてしまいました。
本当に悔しいです…
とりあえずグリッド系の鍛錬から始めてきます。
最後までお読みいただきありがとうございました！
お時間ありましたら、ほかの記事も併せて読んでいってください！
コメント