【AtCoder】ABC231をPython3で解説（ABCD）

ABC231のA-D問題の解説。

目次

A - Water Pressure
B - Election
C - Counting 2
D - Neighbors

A - Water Pressure

解説

水深$x$の場所で$x / 100$となるとき、水深$D$の場所での水圧を求める問題。

単純に$100$で割ればいいだけだが、扱う型をfloatにする点に注意。

コード

def main():
    d = float(input())
    print(d/100)

if __name__ == '__main__':
    main()

B - Election

解説

$N$人の投票があり、それぞれには名前が書いていて、投票数が多かった名前を出力する問題。

この問題は、名前とその数を数える辞書を作成し、辞書の中から投票数の最大値を求め、その名前を出力してあげれば良い。

サンプルコードには、辞書とlambdaを用いたものとリストにはいっている文字列を数えてくれるCounterを用いたものの2つを載せている。

コード1(lambda)

# lambda -> https://note.nkmk.me/python-dict-value-max-min/
def main():
    n = int(input())
    slist = list(input() for _ in range(n))

    cnt = dict()

    for s in slist:
        if s not in cnt:
            cnt[s] = 1
        else:
            cnt[s] += 1

    max_kv = max(cnt.items(), key=lambda x: x[1])
    print(max_kv[0])


if __name__ == '__main__':
    main()

コード2(Counter)

# Counter
def main():
    from collections import Counter

    n = int(input())

    slist = list(input() for _ in range(n))

    cnt_list = Counter(slist)
    ans = cnt_list.most_common()[0][0] # 最も多い文字を出力
    print(ans)

if __name__ == '__main__':
    main()

C - Counting 2

解説

$N$人の身長はそれぞれ$A_i$であるとき、身長が$x_j$以上の生徒は何人いるかを求める問題。

結論から言うと、二分探索をもちいることで問題を解くことができる。
まず、身長が与えられた配列をsorted()またはsort()を用いて、あらかじめ昇順に並び替えをしておく。これらに対して、$x_j$の値が並び替えをした配列の中でどこにあるかを二分探索を用いて求める（先頭から探し出すとTLEしてしまうため）。今回のサンプルコードには、Python用のライブラリbisectを使用しているが、可能ならば自分で実装しても良い。

求めた配列の場所を配列全体のサイズから引いてあげることで、$x_j$以上を満たす$A_i$を求めることができる。

二分探索について詳しく知りたい場合は、過去に記事を作成しているので、そちらを参考に学習していただきたい。

また、別解として尺取法の要領で問題を解くことができる。

コード1(bisect)

# bisect
def main():
    from bisect import bisect_left

    n, q = map(int, input().split())
    alist = list(map(int, input().split()))
    sort_alist = sorted(alist)

    for _ in range(q):
        x = int(input())
        ans = n - bisect_left(sort_alist, x)
        print(ans)

if __name__ == '__main__':
    main()

コード2(尺取like)

def main():
    n, q = map(int, input().split())
    alist = list(map(int, input().split()))
    anlist = []

    for a in alist:
        anlist.append((a, 10**9))

    xlist = []

    for i in range(q):
        x = int(input())
        xlist.append((x, i))

    # Aとxを降順に並び替え
    axlist = sorted(anlist+xlist, reverse=True)

    # debug
    # print(axlist)

    ans = [0] * q
    cnt = 0

    for x, i in axlist:
        if i < q: # xlistの値について
            ans[i] = cnt
        else:
            cnt += 1

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

D - Neighbors

解説

$N$人を横一列に並べるとき、「$A_i$と$B_i$が隣り合っている」という$M$個の条件をすべて満たせるかどうかを判定する問題。

この問題を要約すると、「ここに存在するグラフは、頂点のみかパスグラフ（1つの頂点から出ている辺の数が2以下の、閉路が存在しないグラフ）であるかどうか」を求める問題だ。

様々な解法があるが、今回はUnion-Findを活用する。

まず、条件に対しての$a$と$b$の頂点を数える配列を用意して、入力に対して1つずつ足しておく。
その後、$a$と$b$がつながっているかどうか、また、同じグループに存在しているかどうかをsame()を用いて判定する。もし、つながっていれば、グラフに閉路ができてしまい、横一列という初期条件を満たさないので、その時点でNoを出力する。
その後、$a$と$b$をunion()で接続して、同様のことを繰り返す。

すべての条件に対してこれらが行えれば、頂点を数える配列に着目する。このとき、パスグラフになるためには、頂点から出る辺の数が2以下ではないといけないので、これを判定して答えを出力する。

Union-Findについて詳しく知りたい場合は、過去に記事を作成しているので、そちらを参考に学習していただきたい。

コード

def main():
    from collections import defaultdict

    class UnionFind():
        def __init__(self, n):
            self.n = n
            self.parents = [-1] * n

        def find(self, x):
            if self.parents[x] < 0:
                return x
            else:
                self.parents[x] = self.find(self.parents[x])
                return self.parents[x]

        def union(self, x, y):
            x = self.find(x)
            y = self.find(y)

            if x == y:
                return

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

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

        def size(self, x):
            return -self.parents[self.find(x)]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def members(self, x):
            root = self.find(x)
            return [i for i in range(self.n) if self.find(i) == root]

        def roots(self):
            return [i for i, x in enumerate(self.parents) if x < 0]

        def group_count(self):
            return len(self.roots())

        def all_group_members(self):
            group_members = defaultdict(list)
            for member in range(self.n):
                group_members[self.find(member)].append(member)
            return group_members

        def __str__(self):
            return '\n'.join(f'{r}: {m}' for r, m in self.all_group_members().items())

    n, m = map(int, input().split())

    uf = UnionFind(n)
    degree = [0] * n # 頂点から出ている辺を数えるための配列

    for _ in range(m):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        degree[a] += 1
        degree[b] += 1
        if uf.same(a, b): # 互いがつながっていたらアウト
            print('No')
            exit()
        uf.union(a, b) # 頂点aと頂点bを結合

    if max(degree) <= 2: # ひとつの頂点から3本以上の辺がでていなければ
        print('Yes')
    else:
        print('No')


if __name__ == '__main__':
    main()

編集後記

最近、二分探索やらUnion-Findやらが多い気がするのは気の所為かな？