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

はじめに

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

A-D問題について、自身の復習も兼ねて説明できればと思います。誤った記述やより良い解法などあれば、コメントをいただけると幸いです。

ABC342

A – Yay!

問題

A問題

Sはある1文字を除いて全て同じ文字で構成されています。他のどの文字とも異なる文字は前から何文字目かを求める問題です。

思考の筋道

2重for文を用いて、 i 文字目が他のどの j 文字目とも異なるかどうかを調べればよいでしょう。

すべての文字と比較するのではなく、前後の文字とだけ比較するといった方法もあります。（両端に注意）

コード

S = input()
n = len(S)

for i in range(n):
    flg = True
    for j in range(n):
        if i != j and S[i] == S[j]:
            flg = False
            break
    if flg:
        print(i + 1)

B – Which is ahead?

問題

B問題

N人が1列に並んでおり、人 A_i と B_i のどちらが前に並んでいるかを調べる問題です。

思考の筋道

人 A_i と B_i が配列の何番目かを調べ、それを比較しましょう。

コード

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

for pair in l:
    A, B = pair[0], pair[1]
    id_a = P.index(A)
    id_b = P.index(B)
    if id_a < id_b:
        print(A)
    else:
        print(B)

C – Many Replacement

問題

C問題

英小文字列に対し、ある文字を別の文字に置き換える操作を何度か行った後の文字列を表示する問題です。

思考の筋道

文字列の長さは2×10^5であることから、文字列に各操作を行っていくのでは、TLEになってしまいます。

文字列ではなく、26文字の英小文字に対して各操作を行っていきましょう。これであれば26文字だけなので問題ありません。各英小文字が操作終了時にどの文字に置き換えられているかが得られるので、あとはそれに従って、文字列を変換すればよいです。

コード

import string
N = int(input())
S = input()
Q = int(input())

alphabet = string.ascii_lowercase
goal = string.ascii_lowercase

for i in range(Q):
    c, d = map(str, input().split())
    goal = goal.replace(c, d)

translation = str.maketrans(alphabet, goal)

S = S.translate(translation)
print(S)

D – Square Pair

問題

D問題

非負整数列に対し、積が平方数となる2数のインデックスの組の個数を数える問題です。

思考の筋道

0と、0以外の数で分けて考えます。

0はもう片方の数が何であっても、積が0で平方数になります。しかし、0が複数ある場合は、0×0をダブルカウントしないように注意しましょう。

0以外の数は素因数分解します。各素因数の指数の偶奇を調べましょう。指数が奇数の素因数が完全に一致する2つの数は、掛けると平方数になります。

例
2は、指数が奇数の素因数は2のみ。
72(=2^3×3^2)も、指数が奇数の素因数は2のみ。
この2つの数は、指数が奇数の素因数が一致します。掛けると、すべての素因数の指数が偶数となり、平方数になります。

なお、2つの数について、指数が奇数の素因数が完全に一致するかどうかは、指数が奇数の素因数の積が一致するかどうかで調べることができます。

コード

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

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])
    if temp != 1:
        arr.append([temp, 1])
    return arr

def f(a):
    fac = factorization(a)
    res = 1
    for k, n in fac:
        if n % 2:
            res *= k
    return res

d = dict()
ans = 0
zero_count = 0

for num in A:
    if num == 0:
        ans += N - 1 - zero_count
        zero_count += 1
    else:
        s = f(num)
        if s in d:
            d[s] += 1
        else:
            d[s] = 1

for a in d:
    if d[a] >= 2:
        ans += (d[a] * (d[a] - 1)) // 2

print(ans)