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
#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; }
