ABC455を振り返る

はじめに
振り返り

はじめに

みなさま、どうもこんにちは！
毎度おなじみばるとーくでござります…

というわけで、ABC455の振り返りをやっていきます。
結論から言うと、AとCの2完でした…
あの…グリッドが苦手すぎて草も生えんですわ。
C問題はよく頑張った。まじで。時間かかりすぎだけど。
あとD問題は計算量の壁ががが…

振り返り

A - 455

問題文
整数 A,B,C が与えられます。A=B かつ B=C であるならば Yes を、そうでないならば No を出力してください。
制約
1≤A,B,C≤9
入力される値はすべて整数

A - 455

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

講評

これに対してのコードはこんな感じ

#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分かかったの地味に痛いかもね？
言い訳すると、前回のあれがトラウマで…

ABC454を振り返る

今回からABCやAHCが終わるたびに振り返りブログを書いていきたいなと思いまするはじめに始めに、何で急にそんなことするのかと、何で今までやってこなかったかについて説明しますね…まず、「何で急にそんなことするのか」ですが、これはシンプルに「ネ...

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≤H
1≤w1≤w2≤W
h1≤i≤h2 かつ w1≤j≤w2 を満たすすべての整数 i,j についてマス (i,j) とマス (h1+h2−i,w1+w2−j) は同じ色で塗られている
制約
1≤H,W≤10
H,W は整数
Si は ., # からなる長さ W の文字列

B - Spiral Galaxy

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

講評

なんとこちら、ばるとーくさんパスを選択しております！
AtCoder Sempaiにもこっぴどく叱られております！！
だって…苦手なんだものグリッドぉ～

テンプレを頑張って作ろうってことやな。うん。
それにしても6重ループはやばすぎる。わかってても組めてない自信あり（実装力 is どこ？）

C - Vanish

問題文
整数列 A=(A1,A2,…,AN) が与えられます。
以下の操作をちょうど K 回行った後の A の各要素の和として考えられる最小値を求めてください。
整数 x を選ぶ。Ai=x なる各 i について Ai の値を 0 に置き換える。
制約
1≤K≤N≤3×105
1≤Ai≤109
入力される値はすべて整数

C - Vanish

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

講評

こんなコードを書きました

#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[i];
    sum += A[i];
  }

  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[i] != m) {
      mem.push_back(make_pair(m, num));
      mem.resize(mem.size() + 1);
      m = A[i];
      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[i].first * mem[i].second);
    sub.resize(sub.size() + 1);
    cerr << mem[i].first << mem[i].second << endl;
  }

  sort(sub.rbegin(), sub.rend());

  for (int i = 0; i < k; i++) {
    if (i > sub.size()) {
      break;
    }
    sum -= sub[i];
    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×105
1≤Ci,Pi≤N
操作を順に行ったとき、各操作を行う直前の時点でカード Ci とカード Pi は異なる山にある
操作を順に行ったとき、各操作を行う直前の時点でカード Pi はある山の一番上に積まれている
入力される値はすべて整数

D - Card Pile Query

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

講評

こんなコードを書きました

#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[i].push(i);
    where[i] = i;
  }

  for (int i = 0; i < q; i++) {
    int c, p;
    cin >> c >> p;
    --c;  // 0-indexed
    --p;

    int move = where[c];
    stack<int> tmp;
    while (st[move].top() != c) {//抜く
      tmp.push(st[move].top());
      where[tmp.top()] = p;
      st[move].pop();
      cerr << move << st[move].size() << endl;
    }

    tmp.push(st[move].top());
    where[tmp.top()] = where[p];
    st[move].pop();
    cerr << move << st[move].size() << endl;

    while (tmp.size() != 0) {//足す
      st[where[p]].push(tmp.top());
      tmp.pop();
      cerr << p << st[where[p]].size() << endl;
    }
  }

  for (int i = 0; i < n; i++) {
    cout << st[i].size() << " ";
  }
  cout << "\n";
  return 0;
}

REです。
Claude曰くこうらしいです。

where[i] は「カード i がどの山にあるか」を表す配列。移動先は「カード p のいる山」、つまり where[p] です。ところが上のコードでは where[tmp.top()] = p と、カード番号 p を山番号として代入しています（その下では where[tmp.top()] = where[p] と正しく書かれているのに）。
これにより where[] が壊れ、後続のクエリで存在しない山にアクセスしようとしてREします。

あと、しんぷるにこれだとO(NQ)なのでTLEしちゃうんですよね…
解説聞いて、Claudeと一緒に紐解いたらやっとうなずけました。貴様連結リストかぁ。

おわりに

今日のABCにより、始めてから半年以内に入茶するという目標は潰えてしまいました。
本当に悔しいです…
とりあえずグリッド系の鍛錬から始めてきます。

最後までお読みいただきありがとうございました！
お時間ありましたら、ほかの記事も併せて読んでいってください！