AtCoder abc372 参加メモ

UNIQUE VISION Programming Contest 2024 Autumn (AtCoder Beginner Contest 372) - AtCoder

A - delete .

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  string n; cin >> n;
  for(auto c: n) if (c != '.') cout << c;
  return 0;
}

B - 3^A

m を 3 進数に変換する

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int m; cin >> m;
  vector<int> ans;
  for(int i = 0; m > 0; i++) {
    while(m%3 != 0) { m--; ans.push_back(i); }
    m /= 3;
  }
  cout << ans.size() << endl;
  for(auto v: ans) cout << v << " ";
}

C - Count ABC Again

最初にすべての ABC となる部分文字列を数え上げておき、各クエリでは、影響のある部分の差分を考える

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int f(string& s, int idx) { return s.substr(idx,3) == "ABC"; }

int main() {
  int n,q; cin >> n >> q;
  string s; cin >> s;

  int ans = 0;
  REP(i,n-2) ans += f(s,i);

  REP(_,q) {
    int x; char c; cin >> x >> c; x--;
    for(int i = max(0,x-2); i <= x; i++) ans -= f(s,i);
    s[x] = c;
    for(int i = max(0,x-2); i <= x; i++) ans += f(s,i);

    cout << ans << endl;
  }
  return 0;
}

D - Buildings

難しい。 右端からスタートし、スタックで直近の数え上げ対象となるビルの情報を持っておくようにする。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n; cin >> n;
  vector<int> h(n);
  REP(i,n) cin >> h[i];

  vector<int> ans(n), st;
  for(int i = n-1; i >= 0; i--) {
    ans[i] = st.size();
    // 現在のビルが stack のトップより高い場合
    // stack のトップにあるビルは数え上げ対象にならないため pop する
    while(st.size() && h[st.back()] < h[i]) st.pop_back();
    st.push_back(i);
  }

  for(auto v: ans) cout << v << " ";
  return 0;
}

E - K-th Largest Connected Components

手持ちの UnionFind 構造体に頂点番号管理する処理を追加。 ac library 頼りだったので久々にライブラリを持ち出した。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

struct UnionFind {
  vector<int> d;
  vector<set<int>> st;
  UnionFind(int n = 0): d(n,-1), st(n) {
    REP(i,n) st[i].insert(i);
  }
  int root(int x) {
    return d[x] < 0 ? x : d[x] = root(d[x]);
  }
  int unite(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return 0;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;

    st[x].insert(st[y].begin(),st[y].end());
    while(st[x].size() > 10) st[x].erase(st[x].begin());
    return 1;
  }
  int kth_largest(int u, int k) {
    u = root(u);
    if ((int)st[u].size() < k) return -1;
    auto it = st[u].rbegin();
    advance(it,k-1);
    return *it+1;
  }
};

int main() {
  int n,q; cin >> n >> q;
  UnionFind uf(n);
  REP(_,q) {
    int t,u,v; cin >> t >> u >> v;
    u--; v--;
    if (t == 1) uf.unite(u,v);
    if (t == 2) cout << uf.kth_largest(u,v+1) << endl;
  }
  return 0;
}

雑感

D 問題に詰まって大ブレーキ。典型問題なんだろうけど頭がこんがらがってしまった。

tic40さんのユニークビジョンプログラミングコンテスト2024 秋(AtCoder Beginner Contest 372)での成績:1935位
パフォーマンス:1212相当
レーティング:1184→1187 (+3) :)
#AtCoder #ユニークビジョンプログラミングコンテスト2024秋(ABC372) https://atcoder.jp/users/tic40/history/share/abc372?lang=ja