💨

AtCoder ABC206 個人的メモ

6 min read

所感

abc3完
abc206_score

A - Maxi-Buying

1.08*Nの値をを切り捨てした値が消費税を加算した後の金額となる。
float型を小数点以下切り捨てでint型にするには、組み込み関数int()の引数にfloatを入れればおk

https://docs.python.org/ja/3/library/functions.html#int

浮動小数点の誤差を考慮すると、\lfloor108*N/100\rfloorの方が良かった。

https://qiita.com/u2dayo/items/237424d7f6aff42adb89#a問題maxi-buying
N = int(input())

cal = int(N * 1.08)
if cal < 206:
    print("Yay!")
elif cal > 206:
    print(":(")
else:
    print("so-so")

B - Savings

問題文通りにシミュレーションすればおk。
N=10^9の場合でも解は44721なので、十分時間制限に間に合う。

ループの上限設定間違えて1wa
range関数の引数がNだと、N=1のときにバグる

N = int(input())

coin = 0
for i in range(N + 10):
    coin += i
    if coin >= N:
        break

print(i)

C - Swappable

1つ目の条件(1\leq i<j\leq N)を満たす(i,j)組み合わせは_NC_2通りある。
ここから2つ目の条件を満たさない場合を除く。
ある数がAK個含まれている時、その同じ数同士を選ぶ組み合わせは_KC_2通りある。
よって、各数においてこの値を引いていけばおk.

from math import comb
from collections import Counter

N = int(input())
A = list(map(int, input().split()))

ans = comb(N, 2)
cnt = Counter(A)
for i in cnt.keys():
    ans -= comb(cnt[i], 2)

print(ans)

D - KAIBUNsyo

B=(A_1,A_2,\cdots,A_{\lfloor N/2\rfloor}),C=(A_N,A_{N-1},\cdots,A_{\lceil N/2\rceil+1})とする。
これはBAの前半分、CAの後ろ半分を逆順にしたもの。また、Nが奇数の場合はAの真ん中の数はBCのいずれにも属さない。
この時、(Aを回文にする)=(B=Cとなる)と言えるので、以降はB=Cとする方法を考える。

B_i\not ={C_i}となるiが1つだけならば、そのiでのB_iC_iへ又はC_iB_iへ置換する操作を1回行えば最適となる。
しかし、問題の例1のような場合ではもう少し複雑になる。
例1のABCは以下のようになる。

\begin{aligned} A&=(1,5,3,2,5,2,3,1)\\B&=(1,5,3,2)\\C&=(1,3,2,5) \end{aligned}

B_i\not ={C_i}となっている組み合わせは(B_i,C_i)=(5,3),(3,2),(2,5)の3つ。
この組み合わせの1つ目と2つ目に注目する。
1つ目の組み合わせから53をある同じ数xに、2つ目から32をある同じ数yに置換する必要があると分かる。
ここで問題文より、ある数を置換する際は同じ数を全て置換しなければならないので、ある時に同じ数になっている要素は最終的にも同じ数になっているはず。
よって、1つ目の組み合わせの3と2つ目の3も最終的に同じ数になるはずなので、x=yとなると分かる。
従って、例1では(2,3,5)を同じ数にすれば良いと分かる。
3つ目の組み合わせ(2,5)は、既に両方の要素が(2,3,5)に含まれているのでもう考える必要はない。
(2,3,5)を最小の操作回数で同じ数に置換するには、組み合わせ内のいずれかの数字へと他の数を置換すれば良さそう。
その際の操作回数は((組み合わせの要素数)-1)回。
例1では(2,3,5)の組み合わせのみを置換すれば良いから、解は3-1=2となる。

以上をまとめると以下の実装で解けそう。

  1. B_i\not ={C_i}となっている組み合わせを探す。
  2. 同じ数同士で組み合わせを連結する。
  3. 各組み合わせごとに(組み合わせの要素数)-1を計算する。
  4. その総和が解。

で、要素の連結とか連結後の成分の大きさの計算とかを実装するにはunion-findを使えばおk。

abc206f_figure

class UnionFind:
    """Union-Find(素集合データ構造(disjoint-set data structure)に対しての操作)"""
    def __init__(self, n: int):
        """
        Constructer(Initialize parameter in this class)

        Parameters
        ----------
        n : int
            Number of node

        Yields
        -----
        root : list
            When value is postive, express root of the node.
            When it is negative, express this node is root and size of set.
        """

        self.root = [-1] * n

    def find(self, x: int) -> int:
        """
        Search root of node x

        Parameters
        ----------
        x : int
            node x

        Returns
        -------
        x : int
            Root of node x
        """

        if self.root[x] < 0:
            return x
        self.root[x] = self.find(self.root[x])
        return self.root[x]

    def unite(self, x: int, y: int) -> bool:
        """
        Unite two set including node x and node y into one set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        unite_result : bool
            False : Already two node include same set.
            True  : United
        """

        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x
        return True

    def is_same(self, x: int, y: int) -> bool:
        """
        Determine if x and y are in same set.

        Parameters
        ----------
        x, y : int
            Node number

        Returns
        -------
        result : bool
            Determining result
        """

        return self.find(x) == self.find(y)

    def size(self, x: int) -> int:
        """
        Return size of set including node x.

        Parameters
        ----------
        x : int
            Node number

        Returns
        -------
        Size of set : int
        """

        return self.root[self.find(x)] * -1


N = int(input())
A = list(map(int, input().split()))

union = UnionFind(max(A) + 1)
# 解説文中のB,Cがそれぞれfront、backに対応
front = A[:N // 2]
back = A[-(-N // 2):][::-1]
for i in range(N // 2):
    if front[i] == back[i]:
        continue
    # 手順1.と2.をunion-findで同時に行う
    union.unite(front[i], back[i])

ans = 0
# 各組で重複して計算することが無いようにして総和を計算
seen = set()
for a in A:
    root = union.find(a)
    if root in seen:
        continue
    seen.add(root)
    ans += union.size(root) - 1

print(ans)

参考

問題の解説

https://atcoder.jp/contests/abc206/editorial/2097
https://blog.hamayanhamayan.com/entry/2021/06/19/233819

union-findは↓(ACL登場以前に公式解説動画で使ってたライブラリ)を参考に作っといたライブラリ

https://github.com/atcoder/live_library/blob/master/uf.cpp

pythonでのunion-find解説

https://note.nkmk.me/python-union-find/
https://ikatakos.com/pot/programming_algorithm/data_structure/union_find_tree

Discussion

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