💨

AtCoder ABC206 個人的メモ

2021/06/20に公開

Python

競技プログラミング

AtCoder

tech

所感

abc3完
abc206_score

A - Maxi-Buying

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

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

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つ目の条件を満たさない場合を除く。
ある数が $A$ に $K$ 個含まれている時、その同じ数同士を選ぶ組み合わせは $_KC_2$ 通りある。
よって、各数においてこの値を引いていけばおｋ．

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)

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

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

\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つ目の組み合わせから $5$ と $3$ をある同じ数 $x$ に、2つ目から $3$ と $2$ をある同じ数 $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$ となる。

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

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

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

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)

参考

問題の解説

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

pythonでのunion-find解説
https://note.nkmk.me/python-union-find/

AtCoder ABC206 個人的メモ

所感

A - Maxi-Buying

B - Savings

C - Swappable

D - KAIBUNsyo

参考

Discussion