AtCoder Beginner Contest 120
Updated:
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)];
}
};
参考文献
- “データ構造をマージする一般的なテク” とは？ by 秋葉先生
- AtCoder ABC 120 D - Decayed Bridges (400 点) by けんちょんさん
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