ABC 120
本日の勝敗: int型の敗北
A
B/A
とC
の小さい方
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { int A, B, C; cin >> A >> B >> C; cout << min(B / A, C) << endl; }
B
- 制約が緩いので何も考えずに公約数を全部求めて
K
番目に大きいものを出力した
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { int A, B, K; cin >> A >> B >> K; vector<int> n; FOR(i, 1, min(A, B) + 1) { if (A % i == 0 && B % i == 0) n.push_back(i); } cout << n[n.size() - K] << endl; }
C
0
と1
の個数のうち小さい方の2倍- 片方が残っていたら必ずどこかで隣り合うので、片方が消滅するまで取り除くことができるから
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; int main() { string S; cin >> S; size_t cnt = 0; REP(i, S.size()) { if (S[i] == '0') cnt++; } cout << 2 * min(cnt, S.size() - cnt) << endl; }
D
- UnionFindを知っていますか?というだけの問題……のはずだった
- 終わりから考えて、最初バラバラだった島をつないでいく方針で考える
- 端が全て崩落しているときの不便さは
N*(N-1)/2
- 既に連結している島をつないでも不便さは変わらない
- 連結していない島をつなぐと、それぞれの島群の島数の積だけ不便さが減る
- 方針は一瞬で思いついたのだが、
N<=10^5
なのでN*(N-1)/2
はint型に収まらないのにN
をint型で宣言していたので切り捨てられてしまいWAを連発してしまった。他の人の解説ブログを見てN
の型をlong longに書き直しただけでACだった。
#include <bits/stdc++.h> #define REP(i, n) for (int i = 0; i < (int)(n); ++i) #define FOR(i, k, n) for (int i = (k); i < (int)(n); ++i) typedef long long int ll; using namespace std; struct UnionFind { vector<int> par; vector<int> rank; UnionFind(int n) : par(n), rank(n, 1) { for (int i = 0; i < n; ++i) par[i] = i; } int find(int x) { if (x == par[x]) return x; return par[x] = find(par[x]); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (rank[x] < rank[y]) swap(x, y); par[y] = x; rank[x] += rank[y]; } bool same(int x, int y) { return find(x) == find(y); } int size(int x) { return -rank[find(x)]; } }; int main() { ll N, M; cin >> N >> M; vector<int> A(M), B(M); vector<ll> ans(M); REP(i, M) { cin >> A[i] >> B[i]; A[i]--; B[i]--; } UnionFind uf(N); ans[M - 1] = N * (N - 1) / 2; for (int i = M - 1; i > 0; --i) { if (uf.same(A[i], B[i])) { ans[i - 1] = ans[i]; continue; } ans[i - 1] = ans[i] - uf.size(A[i]) * uf.size(B[i]); uf.unite(A[i], B[i]); } REP(i, M) cout << ans[i] << endl; }