📝

AtCoder Beginner Contest 282レポート

2022/12/19に公開約4,600字

摘要

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

ABC282

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

https://atcoder.jp/users/hannaheptapod/history/share/abc282

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

https://atcoder.jp/contests/abc282/submissions/37323461

B - Let's Get a Perfect Score

B - 問題

N個の長さM文字列A_1, …, 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()

https://atcoder.jp/contests/abc282/submissions/37329930

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

https://atcoder.jp/contests/abc282/submissions/37332937

D - Make Bipartite 2

D - 問題

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

D - 解法

二部グラフの判定について,DSUを用いる方法[1]がググって出てきた(以前にもやったことがあるような気がする).
N\times2色の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()

https://atcoder.jp/contests/abc282/submissions/37340898

E - Choose Two and Eat One

最大全域木を考えるらしい(何それ).

感想

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

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

Discussion

ログインするとコメントできます