目次
AtCoder Beginner Contest 120 B,C,D問題メモ
B - K-th Common Divisor
問題
- 正整数 $A,B$ を共に割り切る、$K$ 番目に大きな正整数を求めよ
- $1 \le A,B \le 100$
解法
もんだいぶん を よく よみましょう（大きい方から $K$ 番目）
解法は単純に全探索でよい。
a, b, k = map(int, input().split())
t = 0
for i in range(100, 0, -1):
if a % i == 0 and b % i == 0:
t += 1
if t == k:
print(i)
break
制約が大きくなっても、「公約数は最大公約数の約数」なので、まずGCDを見つけてから約数を求めると、$O(\sqrt{\min(A,B)})$ くらいで解ける。
C - Unification
問題
- '0'と'1'のみからなる文字列 $S$ がある
- 以下の操作を好きな回数、好きな箇所に適用できる
- '01'または'10'を消す
- 消されてできた隙間を詰める
- 上手く操作をすると、最大何文字消すことが出来るか
解法
最終状態（これ以上消せない状態）がどんなものか考える。
'0'と'1'が両方残っているのにこれ以上消せない状態があるとする。そのような状態は、どこかで'0'と'1'が隣り合っている。ならばそこで消せることになる。
よって矛盾するので、これ以上消せない状態は、'0'か'1'のどちらかは残っていない状態であることが言える。
1回につき'0'と'1'を1個ずつ消すので、最大'0'と'1'の個数の少ない方だけ消すことが出来る。
s = input()
_0 = s.count('0')
_1 = s.count('1')
print(min(_0, _1) * 2)
D - Decayed Bridges
問題
- $N$ 個の島を、$M$ 本の橋が結んでいる
- 橋には $1,2,...,M$ の番号が付き、$i$ 番目の橋は、島 $A_i$ と $B_i$ を結んでいる
- ところが、橋は番号が小さい方から順に崩落していく
- $1 \le i \le M$ について、$i$ 番目の橋が崩落した直後の以下の個数を求めよ
- 互いに行き来することができない島のペアの数
- 順序を入れ替えただけのものは1つと数える
- $2 \le N \le 10^5$
- $1 \le M \le 10^5$
解法
$i$ 番目の橋が落とされた時、いくつの島のペアが行き来不能になったのか？ というのを時系列通りに考えるのは、ちょっとむずい。 探索すれば答えは出るが、制約上、崩落ごとに探索を繰り返していたのでは時間がかかってしまう。
ここはUnionFind木を使って、時系列を逆方向に辿っていくのがよい。分割の問題を結合にすり換える。
全ての孤立した島を、徐々に橋を建設して繋いでいくイメージとなる。 UnionFindを使うと、橋によって行き来可能になる島のペア数の計算がしやすくなる。
最初は、全ての島が孤立しているので $\frac{N(N-1)}{2}$ 個のペアが行き来不能。
そこから遡って $i$ 番目の橋を建設する時は、以下の操作によりペア数を求められる
$A_i$ と $B_i$ が、$i$ 番目の橋を建設前から行き来できていた
$i$ 番目の橋が出来ても、行き来できないペアは変わらない。
$A_i$ と $B_i$ は、$i$ 番目の橋ができて始めて行き来できるようになった
$A_i$ と $B_i$ をUnionする。
「$A_i$ 側に属する島数 × $B_i$ 側に属する島数」だけ、行き来できる島のペアが増えることになる。つまり、行き来できない島のペアが減る。
実装
UnionFindを使いながらも、一工夫が必要。「自身のグループに属する要素の数」を、保持して更新しなければならない。
これは、UnionFind上で親の番号を保持する配列（下記table）で、根要素に自身のグループの要素数を持たせるなどで実装できる。
その際、自身が根であることを区別できるように、要素数は負数で持たせる。
table[i]が正ならその値は $i$ の親の番号、負なら $i$ は根で絶対値はグループの要素数を示すようにする。
もちろん、そうせずとも要素数保存用配列を別に用意してもよい。消費メモリが多少増えるだけで、1つの配列に2つの意味を持たせるよりはわかりやすいコードになる。
要素数を持っておくと、Union時に要素数の少ない方を多い方に繋ぐようにすると、木の平衡状態を保つのにも役立つ。
import sys
class UnionFind:
def __init__(self, n):
self.table = [-1] * n
def _root(self, x):
if self.table[x] < 0:
return x
else:
self.table[x] = self._root(self.table[x])
return self.table[x]
def find(self, x, y):
return self._root(x) == self._root(y)
def union(self, x, y):
r1 = self._root(x)
r2 = self._root(y)
if r1 == r2:
return
d1 = self.table[r1]
d2 = self.table[r2]
if d1 <= d2:
self.table[r2] = r1
self.table[r1] += d2
else:
self.table[r1] = r2
self.table[r2] += d1
n, m = map(int, input().split())
bridges = list(sys.stdin)
bridges.reverse()
buf = [n * (n - 1) // 2]
uft = UnionFind(n)
for line in bridges[:-1]:
a, b = map(int, line.split())
a -= 1
b -= 1
if uft.find(a, b):
buf.append(buf[-1])
continue
ra = uft.table[uft._root(a)]
rb = uft.table[uft._root(b)]
buf.append(buf[-1] - ra * rb)
uft.union(a, b)
buf.reverse()
print('\n'.join(map(str, buf)))
