📝

AtCoder Beginner Contest 282レポート

2022/12/19に公開

Python

AtCoder

tech

摘要

ABCDの4完でした．Dまでスムーズだったのでまずまずのパフォーマンスです．

ABC282

コンテスト名: HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)
順位: 1016th / 8407
パフォーマンス: 1441
レーティング: 1247 → 1268 (+21) Highest更新！
段級位: 4 級
コンテスト参加回数: 67

A - Generalized ABC

A - 問題

英大文字をAから昇順に $K$ 個繋げた文字列を出力せよ．

A - 解法

特筆事項なし．

A - ACコード

def main():
    K = int(input())

    ans = ''.join(chr(ord('A') + i) for i in range(K))
    print(ans)


if __name__ == '__main__': main()

B - Let's Get a Perfect Score

B - 問題

$N$ 個の長さ $M$ 文字列 $A_1, \dots, A_N$ が与えられる．
$1 \leq x < y \leq N$ を満たす整数の組 $(x, y)$ であって， $1 \leq i \leq M$ を満たす任意の整数 $i$ についてA[x][i] == 'o' or A[y][i] == 'o'を満たすものの個数を出力せよ．

B - 解法

大人しく二重ループ．

B - ACコード

def main():
    global N, M, S
    N, M = map(int, input().split())
    S = [input() for _ in range(N)]

    ans = solve()
    print(ans)


def solve():
    ret = 0
    for i in range(N-1):
        si = S[i]

        for j in range(i+1, N):
            sj = S[j]

            for k in range(M):
                if si[k] == 'x' and sj[k] == 'x': break
            else: ret += 1

    return ret


if __name__ == '__main__': main()

C - String Delimiter

C - 問題

長さ $N$ の文字列 $S$ について， $2i-1$ 番目と $2i$ 番目の"の間にある,を.に置換した文字列を出力せよ．

C - 解法

$S$ を左から順に見ていき，括られているかどうかをフラグで管理しながら操作を行う．

C - ACコード

def main():
    N = int(input())
    S = input()

    ans = solve(N, S)
    print(ans)


def solve(N, S):
    arr = ['']*N

    is_closed = False
    for i, si in enumerate(S):
        if si == '"': is_closed = not is_closed
        if si == ',' and not is_closed: si = '.'

        arr[i] = si

    return ''.join(arr)


if __name__ == '__main__': main()

D - Make Bipartite 2

D - 問題

$N$ 頂点 $M$ 辺の単純無向グラフ $G$ について， $1 \leq u < v \leq N$ を満たす整数の組 $(u, v)$ であって， $G$ に辺 $(u, v)$ を追加した時に $G$ が単純かつ二部グラフになるような辺の個数を出力せよ．

D - 解法

二部グラフの判定について，DSUを用いる方法^[1]がググって出てきた（以前にもやったことがあるような気がする）．
$N$ 個 $\times$ $2$ 色の $2N$ 要素をもつdsuを用意し， $G$ の各辺に対し，両端の頂点についてそれぞれ反対の色の要素同士をdsu.merge()する．

ここから条件を満たす $(u, v)$ の組み合わせを数えるのに，余事象が使えそう．
つまり，

すでに辺がある $M$ 個
dsuの各連結成分内において，同じ色が塗られている $2$ 頂点の組み合わせ

を $\binom{N}{2}$ から引けばよい．

D - ACコード

from bisect import bisect_left


def main():
    global N, M, edges
    N, M = map(int, input().split())
    edges = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(M)]

    ans = solve()
    print(ans)


def solve():
    dsu = DSU(2*N)

    for u, v in edges:
        dsu.merge(u, v+N)
        dsu.merge(u+N, v)

    for i in range(N):
        if dsu.same(i, i+N): return 0

    ret = N*(N-1)//2 - M
    for g in dsu.groups():
        cnt = bisect_left(g, N)
        ret -= cnt*(cnt-1)//2

    return ret


class DSU:
    def __init__(self, n):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        x, y = self.leader(a), self.leader(b)
        if x == y: return x
        if -self.parent_or_size[x] < -self.parent_or_size[y]: x, y = y, x
        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x
        return x

    def same(self, a, b):
        assert 0 <= a < self._n
        assert 0 <= b < self._n
        return self.leader(a) == self.leader(b)

    def leader(self, a):
        assert 0 <= a < self._n
        if self.parent_or_size[a] < 0: return a
        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a):
        assert 0 <= a < self._n
        return -self.parent_or_size[self.leader(a)]

    def groups(self):
        leader_buf = [self.leader(i) for i in range(self._n)]
        result = [[] for _ in range(self._n)]
        for i in range(self._n): result[leader_buf[i]].append(i)
        return [r for r in result if r != []]


if __name__ == '__main__': main()

E - Choose Two and Eat One

最大全域木を考えるらしい（何それ）．

感想

D問題まででちょうど30分だったのでまあまあのパフォーマンスでした．
しかし，こういう時に限ってE問題が青Diffなんですね．

脚注

https://noshi91.hatenablog.com/entry/2018/04/17/183132 ↩︎