Kazune Takahashi

Ygnaiih… ygnaiih… thflthkh’ngha

AtCoder Beginner Contest 120

Updated:

AtCoder Beginner Contest 120

Source codes

Solutions

A - Favorite Sound

$\min(C, B/A)$ を出力する。ただし除算は計算機の割り算。

B - K-th Common Divisor

$M = \min(A, B)$ とする。 $i = M, \dots, 1$ に対して、 $A \% i = 0$ かつ $B \% i = 0$ ならば $K {- -}$ とする。 $K = 0$ ならば $i$ を出力して終了する。

ポイント

大きい方からやることに注意。ここで時間を食うという…

C - Unification

操作完了後に最終的にできる文字列は 00...0 または 11...1 の形しかありえない。そうでなければ 01 または 10 のどちらかが存在するのでまだ操作できる。

ゆえに、それまでに消した文字数は、 $a _ 0 = $ 0 の個数、 $a _ 1 = $ 1 の個数としたときに $2 \min(a _ 0, a _ 1)$ である。

ポイント

最終結果 を思い浮かべれば明らかなことなのに、アホなことをやってしまった。

D - Decayed Bridges

時系列を逆にして、だんだん橋をかけていくことにする。島を点とし、橋を辺とするグラフを考察する。最初の不満足度は $N(N-1)/2$ である。 $(A _ i, B _ i)$ をかけると、以下のように不満度が変化する。

  • $A _ i$ と $B _ i$ が連結している場合は不満度は変わらない。
  • $A _ i$ と $B _ i$ が連結している場合は不満度は $X[A _ i] \times X[B _ i]$ だけ減る。ここで $X[k] = $ 点 $k$ の連結成分に含まれる点の個数。

そこで $X[k]$ を高速に応答できればよろしい。いくつか方法があるが、私は「データ構造をマージする一般的なテク」を思い出したのでこれを使った。詳細は秋葉先生の記事を参照。

ポイント

vector<int> ans; と宣言していたせいで WA を 2 回も出してしまった。

Union-Find を使ってもできる

事実上マージテクと変わらないが、サイズが応答できる Union-Find だと思えば良い。けんちょんさんの実装とほぼ同じである。

class UnionFind
{
public:
  vector<long long> par;

  UnionFind(int n) : par(n, -1) {}
  void init(int n)
  {
    par.assign(n, -1);
  }

  int root(int x)
  {
    if (par[x] < 0)
    {
      return x;
    }
    return par[x] = root(par[x]);
  }

  bool is_same(int x, int y)
  {
    return root(x) == root(y);
  }

  bool merge(int x, int y)
  {
    x = root(x);
    y = root(y);
    if (x == y)
    {
      return false;
    }
    if (par[x] > par[y])
    {
      swap(x, y);
    }
    par[x] += par[y];
    par[y] = x;
    return true;
  }

  long long size(int x)
  {
    return -par[root(x)];
  }
};

参考文献

Others

ひどすぎワロタ。私は ABC むしろ不得意なのではないかね。

A - sample: 3, tle: 2.000, time: 01:47, from_submit: 36:34
B - sample: 3, tle: 2.000, time: 03:33, from_submit: 33:02
C - sample: 3, tle: 2.000, time: 05:27, from_submit: 13:06
D - sample: 3, tle: 2.000, time: 27:35, from_submit: 00:00

You May Also Enjoy