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

programming_algorithm/contest_history/atcoder/2019/0303_abc120.txt · 最終更新: 2019/03/04 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0