はじめに
AtCoderの勉強を始めたので、備忘録がてら応用できそうで印象に残った問題の解説記事を投稿していこうと思います。
この記事では、初めて自分が参加したコンテストのAtCoder Beginner Contest 342 D - Square Pairについて解説していきます。
自己紹介
文系大学出身、数学は大学受験レベル、Webエンジニア3年目
Webアプリ開発とWebApi+アプリ開発を主に業務行っています。
言語はRuby,JavaScript,Swift,Go,Kotlinの経験があります。
AtCoderの勉強は始めたばかりでコンテストもABC342(2024/02/24開催)が初参加。
AtCoderではPythonを使っています。
問題の概要
与えられた非負性数列から、積が平方数になる整数ペアの数を求める問題です
考えたこと
ある整数が平方数である条件は「素因数の指数が全て偶数である」と考えることができます。
例えば60は2**2 * 3**1 * 5**1となり2,5の指数が偶数でないため平方数ではありません。
144であれば2**4 * 3**2となって、全ての素因数の指数が偶数なため平方数であるといえます。
そこで今回は、与えられた非負整数配列に対して素因数分解を行い、指数を偶数にすることができるペアの数を求めるという方向で考えていきます。
提出したコード
import sys
from collections import defaultdict
# エラトステネスの篩を用いてn以下の最小素因数を格納した配列を返す
def sieve(n):
spf = list(range(n + 1))
for i in range(2, int(n**0.5) + 1):
if spf[i] == i:
for j in range(i * i, n + 1, i):
if spf[j] == j:
spf[j] = i
return spf
# xを素因数分解する
def factorize(x, spf):
res = []
while x != 1:
factor = spf[x]
count = 0
while x % factor == 0:
x //= factor
count += 1
res.append([factor, count])
return res
N = int(sys.stdin.readline())
l = list(map(int, sys.stdin.readline().split()))
spf = sieve(max(l))
# 奇数回出現する素因数のリスト
odd_factor_lists = []
for num in l:
if num != 0:
factors_with_exponents = factorize(num, spf)
of = []
for factor, exponent in factors_with_exponents:
if exponent % 2 != 0:
of.append(factor)
odd_factor_lists.append(of)
# 奇数回出現する素因数のパターンに基づくカウント
odd_factors_count = defaultdict(int)
for odd_factors_list in odd_factor_lists:
pattern = tuple(odd_factors_list)
odd_factors_count[pattern] += 1
zero_count = l.count(0)
# 0と0以外の要素のペアの数と0同士のペアの数をカウント
count = zero_count * (N - zero_count) + zero_count * (zero_count - 1) // 2
# 奇数回出現する素因数のパターンに基づくペアの数をカウント
for v in odd_factors_count.values():
count += v * (v - 1) // 2
print(count)
終わりに
最後まで読んでいただきありがとうございます。
Python、AtCoder共に初心者なので、より良い解法やコードがあればコメントでご指摘いただけると嬉しいです。
とりあえず、入茶を目指して頑張ります。
03/01追記
よりコードがシンプルになる解法があったので、それについても記事を書いています。合わせてご覧ください。