ABC 120

本日の勝敗: int型の敗北

A

A - Favorite Sound

  • 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

B - K-th Common Divisor

  • 制約が緩いので何も考えずに公約数を全部求めて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

C - Unification

  • 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

D - Decayed Bridges

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