−目次

AtCoder Beginner Contest 120 B,C,D問題メモ

AtCoder Beginner Contest 120 B,C,D問題メモ

AtCoder Beginner Contest 120

AtCoder Beginner Contest 120 解説放送 - YouTube

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)))

            

        
      

−目次