結果
22分59秒(1WA)で全完。140位だった。WAなければ100位以内という前回と同じパターンか。
A問題
はい。
#include"bits/stdc++.h" using namespace std; using ll = int64_t; int main() { ll A, B, C; cin >> A >> B >> C; cout << min(B / A, C) << endl; }
B問題
どうあがいても全探索で殴ればいいいつものB問題。最初小さい方から数えて番目を出力するコードを書いてしまっていた。初期化もmin(A, B)
で良いのに無駄にmax(A, B)
から探し始めてしまった。
#include"bits/stdc++.h" using namespace std; using ll = int64_t; int main() { ll A, B, K; cin >> A >> B >> K; ll num = 0; for (ll i = max(A, B); ; i--) { if (A % i == 0 && B % i == 0) { if (++num == K) { cout << i << endl; return 0; } } } }
C問題
最初「赤赤」または「青青」が消せるのかと誤読していた。どちらにしてもスタックに詰みながら貪欲に考えていけばなんかできそうと証明のないままに提出してAC。
#include"bits/stdc++.h" using namespace std; using ll = int64_t; int main() { string S; cin >> S; ll ans = 0; stack<char> st; for (char c : S) { if (st.empty() || st.top() == c) { st.push(c); } else { st.pop(); ans += 2; } } cout << ans << endl; }
D問題
パッと見で後ろから考えるやつだろうなぁと思うし、サイズが求められるUnionFindを使えばそれでいけそうと考える。ライブラリで持ってるUnionFindはサイズが求められないやつだったので少し改良して提出。そこそこWAが出る。同じときは答えを減らしてはいけないんだった。修正して投げてAC。典型感が強い。
#include"bits/stdc++.h" using namespace std; using ll = int64_t; class UnionFind { public: UnionFind(ll n) { par_.resize(n, -1); } //根を求める ll find(ll x) { return (par_[x] < 0 ? x : par_[x] = find(par_[x])); } //xとyの属する集合を併合 void unite(ll x, ll y) { x = find(x); y = find(y); if (x == y) { return; } par_[x] += par_[y]; par_[y] = x; } //xが属する集合のサイズを取得 ll size(ll x) { return -par_[find(x)]; } //xとyが同じ集合に属するか否かを判定 bool same(ll x, ll y) { return (find(x) == find(y)); } private: vector<ll> par_; }; int main() { ll N, M; cin >> N >> M; vector<ll> A(M), B(M); for (ll i = 0; i < M; i++) { cin >> A[i] >> B[i]; A[i]--; B[i]--; } UnionFind uf(N); vector<ll> ans(M); ans[M - 1] = N * (N - 1) / 2; for (ll i = M - 1; i > 0; i--) { if (uf.same(A[i], B[i])) { ans[i - 1] = ans[i]; continue; } ll size1 = uf.size(A[i]); ll size2 = uf.size(B[i]); ans[i - 1] = ans[i] - size1 * size2; uf.unite(A[i], B[i]); } for (auto a : ans) { cout << a << endl; } }