22
Help us understand the problem. What are the problem?

posted at

updated at

【AtCoder解説】PythonでABC206のA,B,C,D問題を制する!

ABC206A,B,C,D問題を、Python3でなるべく丁寧に解説していきます。

ただ解けるだけの方法ではなく、次の3つのポイントを満たす解法を解説することを目指しています。

  • シンプル:余計なことを考えずに済む
  • 実装が楽:ミスやバグが減ってうれしい
  • 時間がかからない:パフォが上がって、後の問題に残せる時間が増える

ご質問・ご指摘はコメントツイッターまでどうぞ!
Twitter: u2dayo

よかったらLGTMしていただけると、私のやる気がでます!

目次

ABC206 まとめ
A問題『Maxi-Buying』
B問題『Savings』
C問題『Swappable』
D問題『KAIBUNsyo』

アプリ AtCoderFacts を開発しています

コンテストの統計データを見られるアプリ『AtCoderFacts』を作りました。
現在のところ、次の3つのデータを見ることができます。

- レート別問題正解率
- パフォーマンス目安
- 早解きで上昇するパフォーマンス

今後も機能を追加していく予定です。使ってくれると喜びます。

ABC206 まとめ

全提出人数: 9102人

パフォーマンス

パフォ AC 点数 時間 順位(Rated内)
200 AB---- 300 9分 6613(6380)位
400 ABC--- 600 61分 5363(5132)位
600 ABC--- 600 33分 4365(4135)位
800 ABC--- 600 17分 3363(3135)位
1000 ABCD-- 1000 82分 2455(2234)位
1200 ABCD-- 1000 44分 1724(1508)位
1400 ABCD-- 1000 26分 1183(972)位
1600 ABCD-- 1000 15分 795(593)位
1800 ABCDE- 1500 83分 512(337)位
2000 ABCDE- 1500 52分 333(177)位
2200 ABCDE- 1500 31分 227(87)位
2400 ABCDEF 2100 103分 151(40)位

色別の正解率

人数 A B C D E F
4197 98.4 % 93.8 % 47.8 % 5.1 % 0.3 % 0.1 %
1635 99.7 % 99.4 % 93.9 % 27.7 % 1.4 % 0.0 %
1181 99.5 % 99.5 % 98.9 % 69.6 % 5.7 % 0.1 %
733 99.6 % 99.7 % 99.7 % 91.7 % 20.9 % 1.2 %
344 99.7 % 99.7 % 100.0 % 98.3 % 57.9 % 14.8 %
179 93.3 % 93.8 % 93.3 % 93.8 % 69.3 % 49.2 %
43 97.7 % 97.7 % 100.0 % 100.0 % 88.4 % 93.0 %
14 92.9 % 92.9 % 92.9 % 92.9 % 85.7 % 100.0 %

表示レート、灰に初参加者は含めず

私(うにだよ)の結果

screenshot.39.png

Eが解けないとレートが増えませんね。

A問題『Maxi-Buying』

問題ページA - Maxi-Buying
コーダー正解率:98.4 %
コーダー正解率:99.7 %
コーダー正解率:99.5 %

考察

$\lfloor 1.08 \times N \rfloor$ はそのまま計算せずに、$108\times{N}$ を $100$ で割って切り捨てたほうが良いです。

浮動小数点数を使った計算は、値が大きくなると誤差が無視できなくなり、WAになる恐れがあるからです。(この問題では、値が小さいために使っても問題ありません)

コード

def main():
    N = int(input())
    x = N * 108 // 100
    if x < 206:
        print('Yay!')
    elif x == 206:
        print("so-so")
    else:
        print(":(")


if __name__ == '__main__':
    main()

B問題『Savings』

問題ページB - Savings
コーダー正解率:93.8 %
コーダー正解率:99.4 %
コーダー正解率:99.5 %

考察

制約が $N\le10^9$ と小さいので、whileループでシミュレーションすれば解くことができます。

$1+2+\dots+k = \frac{k(k+1)}{2}$ です。つまり、$k$ 日目の貯金額は、 $k$ の二乗の半分くらいになります。したがって、$N=10^9$ であっても、$10^5$ 日目よりは答えが小さくなると予想できます。なぜなら、$\frac{(10^5)^2}{2} = \frac{10^{10}}{2}\gt{10^9}$ だからです。

コード

def main():
    def solve():
        money = 0
        day = 1
        while True:
            money += day
            if money >= N:
                return day
            day += 1

    N = int(input())
    print(solve())


if __name__ == '__main__':
    main()

おまけ : N が非常に大きい場合

$N$ がより大きく、例えば$N\le{10^{18}}$ といった場合、シミュレーションで解くことはできません。

この場合、C問題レベルになりますが、二分探索というアルゴリズムを使うと解くことができます。

C問題『Swappable』

問題ページC - Swappable
コーダー正解率:47.8 %
コーダー正解率:93.9 %
コーダー正解率:98.9 %

考察

すべての $i, j$ の組を試すと計算量が $O(N^2)$ になるので、TLEになります。

$i<j$ という条件があるので、左から順番に見ていくことにします。

今、左から $j$ 番目の $A_j$ を見ているとします。$i<j$ となる $i$ は $1,2,\dots,j-1$ の $j-1$ 個あります。($A_j$ より左側にある要素は $j-1$ 個ありますね)これら $j-1$ 個の整数 $A_1, A_2,\dots,A_{j-1}$のうち、$A_i\ne{A_j}$ であるものがいくつあるか知りたいです。

そのために、今までどの整数が何回出てきたかを数えておきます。ある $j$ に対する答えは、 $j-1$ 個から、$A_j$ と同じ値が何回出てきたかを引けば求められます。

実装

数を数えるときは、collectionsモジュールのCounterを使いましょう。

コード

def main():
    from collections import Counter

    N = int(input())
    A = list(map(int, input().split()))
    C = Counter()  # C[x]: 今までxが何回出現したか

    ans = 0
    for j in range(N):
        ans += j - C[A[j]]  # j=0 から数えているので、今まで見た整数はj個です
        C[A[j]] += 1  # A[j]の出現回数を1増やします
    print(ans)


if __name__ == '__main__':
    main()

D問題『KAIBUNsyo』

問題ページD - KAIBUNsyo
コーダー正解率:5.1 %
コーダー正解率:27.7 %
コーダー正解率:69.6 %

疲れたので軽い説明にさせてください、ごめんね!

考察

無向グラフを考えます。頂点は数字で、同じ数字でなければならない頂点同士を辺で結びます。(回文ですから、前から $i$ 番目と後ろから $i$ 番目の要素が同じ必要があります)

この無効グラフで、連結な頂点同士はすべて同じ数字にしなければなりません。ある連結成分をすべて同じ数字にするには、『連結成分の個数 - 1』個の数字を書き換える必要があります。

したがって、すべての連結成分について、『連結成分の個数 - 1』を足し合わせたものが答えになります。

ある要素と要素が連結かどうかを管理するには、UnionFindというデータ構造を使うのが楽です。

コード

class UnionFind:
    """
    0-indexed
    """

    from typing import List

    def __init__(self, n):
        self.n = n
        self.parent = [-1] * n

    def unite(self, x, y) -> int:
        """
        xとyを併合
        """

        x = self.root(x)
        y = self.root(y)

        if x == y:
            return 0

        if self.parent[x] > self.parent[y]:
            x, y = y, x

        self.parent[x] += self.parent[y]
        self.parent[y] = x

        return self.parent[x]

    def is_same(self, x, y) -> bool:
        """
        xとyが同じ連結成分か判定
        """
        return self.root(x) == self.root(y)

    def root(self, x) -> int:
        """
        xの根を取得
        """
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def size(self, x) -> int:
        """
        xが属する連結成分のサイズを取得
        """
        return -self.parent[self.root(x)]

    def all_sizes(self) -> List[int]:
        """
        全連結成分のサイズのリストを取得
        計算量: O(N)
        """
        sizes = []

        for i in range(self.n):
            size = self.parent[i]
            if size < 0:
                sizes.append(-size)
        return sizes

    def groups(self) -> List[List[int]]:
        """
        全連結成分のサイズの内容のリストを取得
        計算量: O(N・α(N))
        なんでACLはO(N)でできるんでしょうね
        """
        groups = dict()

        for i in range(self.n):
            p = self.root(i)
            if not groups.get(p):
                groups[p] = []
            groups[p].append(i)

        return list(groups.values())


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

    def solve():
        Const = 2 * 10 ** 5 + 5
        uf = UnionFind(Const)
        if N % 2 == 0:
            first = A[:N // 2]
            second = A[N // 2:][::-1]
        else:
            # 数列の長さが奇数の場合、中央の要素はなんでも良いので省きます
            first = A[:N // 2]
            second = A[N // 2 + 1:][::-1]

        for x, y in zip(first, second):
            uf.unite(x, y)

        ans = 0
        for x in uf.all_sizes():
            ans += x - 1
        return ans

    print(solve())


if __name__ == '__main__':
    main()
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Sign upLogin
22
Help us understand the problem. What are the problem?