ABC292 A-D問題の解説（Python）

はじめに

AtCoder Beginner Contest（略称：ABC）とは、AtCoderが週末に開催している、初級者向け？の競技プログラミングコンテストのことです。

参加者はレーティングによってランク分けされます。私は8ランクあるうち、下から2番目のランク（茶色）のため、まだまだひよっこです。一つ上のランク（緑色）を目指して、現在精進しています。

ABCでは毎回8題の問題が出題され、後半の問題ほど、難易度が高くなります。ここでは私が戦える前半4題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC292

A – CAPS LOCK

問題

A問題

英小文字のみからなる文字列の文字をすべて英大文字にする問題です。

解説

upper()メソッドを使うのみです。

コード

S = input()
print(S.upper())

B – Yellow and Red Card

問題

B問題

サッカーで選手がイエローカード、レッドカードによって退場したかどうかを調べる問題です。

解説

イエローカードは2回で退場、レッドカードは1回で退場です。

イエローカードは1点分のペナルティ、レッドカードは2点分のペナルティとし、2点以上のペナルティを受けている選手は退場処分を受けていると考えましょう。

コード

from sys import stdin
N, Q = map(int, input().split())
l = [list(map(int, stdin.readline().split())) for _ in range(Q)]

# N人のペナルティ点数を管理
s = [0] * N

for event in l:
    a, x = event[0], event[1]
    if  a == 1:
        # イエローカードはペナルティ1点
        s[x - 1] += 1
    elif a == 2:
        # レッドカードはペナルティ1点
        s[x - 1] += 2
    else:
        # ペナルティ2点以上の選手は退場
        if s[x - 1] >= 2:
            print("Yes")
        else:
            print("No")

C – Four Variables

問題

C問題

AB+CD=N を満たす正整数(A, B, C, D)の個数を数える問題です。

解説

N <= 2 * 10^5 ですので、多重ループに気をつける必要があります。

AB が定まれば、CD も一意に定まりますので、AB 側のみループさせましょう。

AB が定まっている状態での、正整数(A, B)の個数は、AB の正の約数の個数と同じです。

AB=i , CD = N – i となる正整数(A, B, C, D)の個数は、(i の正の約数の個数)×(N – i の正の約数の個数)となります。

i は 1 から N – 1 までの値を取りますので、はじめに 1 から N – 1 までの正の約数の個数を全て求めておくとよいでしょう。

i の正の約数の個数を数えるのに、i を 1 から i までのすべての数字 j で割っていく方法をとると、TLE(実行制限時間超過)となってしまいます。10^5 レベルのループを i と j で2重に行っているためです。

1 から i までのすべての数字を調べるのではなく、1 から √i までの数字のみを調べるようにしましょう。こうすることで、 j 側のループを10^2 レベルに抑えることができます。

具体例
　16の正の約数の個数を調べるには、1 から 4 までの数字のみ調べればよいです。
　16 は 1 で割り切れるので、1と16で約数2個。
　16 は 2 で割り切れるので、2と8で約数2個。
　16 は 3 で割り切れない。
　16 は 4 で割り切れ、4の2乗が16なので、4のみで約数1個。
　約数は2+2+1=5個とわかります。
　5〜16の数字で割り切れるか調べる必要はありません。

1 から N – 1 までの正の約数の個数を効率的に求めておくことで、この問題を解くことができました。

コード

# C - Four Variables
N = int(input())

# 約数の個数を求める関数
def countDivisor(i):
    count = 0
    for j in range(1, int(i ** 0.5) + 1):
        if i % j == 0:
            if j * j < i:
                count += 2
            else:
                count += 1
    return count

l = [countDivisor(i) for i in range(1, N)]

ans = 0
for i in range(1, N):
    ans += l[i - 1] * l[N - i - 1]

print(ans)

D – Unicyclic Components

問題

D問題

N 頂点 M 辺の無向グラフのすべての連結成分において、その連結成分に含まれる頂点の個数と辺の本数が等しいか判定する問題です。　

解説

連結成分の管理にはUnion-Find木を活用しましょう。

【参考】Union-Find とは（外部リンク）
【参考】Union-Find の実装（外部リンク）

今回の問題では、各連結成分の頂点の個数と辺の本数を求める必要があります。

2頂点を辺で繋ぐ際、その2頂点の連結成分が繋ぐ前から同一であった場合、連結成分の頂点の個数は変わらず、辺の本数はプラス1 されます。

一方、2頂点の連結成分が繋ぐ前は別々であった場合、繋ぐことで一つの連結成分になるので、頂点の個数は各連結成分の頂点の個数の和となり、辺の本数は各連結成分の辺の本数の和プラス1となります。

この計算によって、各連結成分の頂点の個数と辺の本数を求められるので、この問題を解くことができました。

コード

from sys import stdin

class UnionFind():
    # 初期化
    def __init__(self, n):
        self.n = n
        self.par = [-1] * (n + 1)
        self.rank = [0] * (n + 1)
        self.siz = [1] * (n + 1)
        self.edg = [0] * (n + 1)

    # 根を求める
    def root(self, x):
        if self.par[x] == -1:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    # x を含むグループと y を含むグループを併合する
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        if rx == ry:
            self.edg[rx] += 1
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.par[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.siz[rx] += self.siz[ry]
        self.edg[rx] += self.edg[ry] + 1
        return True

    # x を含むグループの頂点の個数を求める
    def size(self, x):
        return self.siz[self.root(x)]

    # x を含むグループの辺の本数を求める
    def edge(self, x):
        return self.edg[self.root(x)]

N, M = map(int, input().split())
l = [list(map(int, stdin.readline().split())) for _ in range(M)]

uf = UnionFind(N)
for edge in l:
    uf.unite(edge[0], edge[1])

for i in range(1, N + 1):
    if uf.size(i) != uf.edge(i):
        print("No")
        exit()
print("Yes")