AtCoder abc304 参加メモ

AtCoder UnionFind 二分探索

Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 304) - AtCoder

B - Subscribers

問題文の通りにやる。 条件がたくさんあるが、よく見ると桁が増えて行く以外は同じ処理だとわかるのでうまくループ処理にするといい。n から x の位以下の数字の切り捨てる処理は、 n / (10x) * (10x) で可能

#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;
  int now = 1e3, x = 1;
  while(1) {
    if (n < now) { cout << n/x*x; return 0; }
    now *= 10; x *= 10;
  }
  return 0;
}

C - Virus

  • ユークリッド距離は平方根を取らずに整数で扱うようにする
  • 初期に感染している人 1 から隣接行列のグラフで BFS して新規感染者がいなくなったら終了する
#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,d; cin >> n >> d;
  d *= d;
  vector<int> x(n),y(n);
  REP(i,n) cin >> x[i] >> y[i];

  vector dist(n,vector<int>(n)); // dist[i][j] := i から j の距離。前計算しておく
  REP(i,n) REP(j,n) dist[i][j] = pow(x[i]-x[j],2) + pow(y[i]-y[j],2);

  vector<bool> ans(n); // 感染していたら true
  ans[0] = true;
  queue<int> q;
  q.push(0);
  while(q.size()) {
    int v = q.front(); q.pop();
    REP(i,n) {
      if (ans[i]) continue;
      if (dist[v][i] > d) continue;
      q.push(i);
      ans[i]=true;
    }
  }

  REP(i,n) cout << (ans[i] ? "Yes" : "No") << endl;
  return 0;
}

D - A Piece of Cake

それぞれのピースにイチゴが何個乗っているか？を高速に求めたい。 n 個のイチゴがどのピースに乗っているかは a, b を二分探索することで logA + logB で求められる。そしたら最大、最小が答えとなるが、イチゴが乗っているピースが (A+1)(B+1) 以下である場合は最小が0(イチゴが1つも乗っていないピースが存在する)となるので注意する。

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

int main() {
  int w,h,n; cin >> w >> h >> n;
  vector<P> s(n);
  REP(i,n) {
    int p,q; cin >> p >> q;
    s[i] = {p,q};
  }
  int x; cin >> x; vector<int> a(x);
  REP(i,x) cin >> a[i];
  int y; cin >> y; vector<int> b(y);
  REP(i,y) cin >> b[i];

  auto f = [&](int i) -> P {
    auto [nx,ny] = s[i];
    int aid = upper_bound(a.begin(),a.end(),nx) - a.begin() - 1;
    int bid = upper_bound(b.begin(),b.end(),ny) - b.begin() - 1;
    return P(aid,bid);
  };

  map<P,int> mp; // どのピースにイチゴが何個乗っているか
  REP(i,n) mp[f(i)]++;
  vector<int> cnt;
  for(auto [_,v]: mp) cnt.push_back(v);

  ll tot = (ll)(x+1)*(y+1);
  int mn = ((ll)mp.size() < tot) ? 0 : *min_element(cnt.begin(),cnt.end());
  int mx = *max_element(cnt.begin(),cnt.end());

  printf("%d %d\n", mn, mx);
  return 0;
}

E - Good Graph

DSU で k 個の良いグラフでなくなるケースを、連結成分の代表元のペアの集合で持っておく。

Q 個の質問で、新たに結合する頂点の代表元のペアが上記の集合に存在した場合は良いグラフでなくなるため No、なければ Yes

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

int main() {
  int n,m; cin >> n >> m;
  dsu uf(n);
  REP(i,m) {
    int u,v; cin >> u >> v;
    u--; v--;
    uf.merge(u,v);
  }

  set<P> st;
  int k; cin >> k;
  REP(i,k) {
    int x,y; cin >> x >> y;
    x--; y--;
    int l1 = uf.leader(x), l2 = uf.leader(y);
    if (l1 > l2) swap(l1,l2);
    st.emplace(l1,l2);
  }

  int q; cin >> q;
  REP(i,q) {
    int u,v; cin >> u >> v;
    u--; v--;
    int l1 = uf.leader(u), l2 = uf.leader(v);
    if (l1 > l2) swap(l1,l2);
    cout << (st.count({l1,l2}) ? "No" : "Yes") << endl;
  }
  return 0;
}