[Python]AtCoder Beginner Contest 162を解いてみた(A~C)

AtCoder Beginner Contest 162にPythonで参加しました。

A – Lucky 7
1. 問題
2. 自分の回答
B – FizzBuzz Sum
1. 問題
2. 自分の回答
C – Sum of gcd of Tuples (Easy)
1. 自分の回答(誤)
2. 自分の回答(正)
感想

A – Lucky 7

問題

3桁の整数Nが与えられます。Nのいずれかの桁に数字の7は含まれますか？
含まれるなら Yes を、含まれないなら No を出力してください。

自分の回答

x = input()
if x.count("7") != 0:
  print("Yes")
else:
  print("No")

7の数を数えて、7の個数が0個出なかったら”Yes”を出力すればいいですね。

B – FizzBuzz Sum

問題

FizzBuzz列 a1,a2,…a1,a2,… を次のように定めます。

iが3でも5でも割り切れるなら、ai=FizzBuzz
そうではなくiが3で割り切れるなら、ai=Fizz
そうではなくiが5で割り切れるなら、ai=Buzz
そうではないなら、ai=i

FizzBuzz列の N項目までに含まれる数の和を求めてください。

自分の回答

x = int(input())
ans = 0

for i in range(1, x + 1):
  if i % 3 != 0 and i % 5 != 0:
    ans += i
print(ans)

有名なFizzBuzzの変わり種の問題ですね。
3で割り切れない、かつ5で割り切れない値を足していけばいいですね。rangeの範囲をx+1とすることを忘れないようにしましょう、、、。

C – Sum of gcd of Tuples (Easy)

自分の回答(誤)

# 誤回答
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
ans = 0

for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      ans += gcd(i, j, k)
      print(i, j , k, gcd(i, j, k))

print(ans)

まずは、間違いから見ていきましょう。これでも正しい値が出力されますが、実行時間超過となり、不正解になります。うん、そんな気がしていました。forを三重にした時は、何か工夫をしないと大抵は時間超過になります。なので、どうにかして、軽くしなければいけません。

自分の回答(正)

# 正解
import math

K = int(input())
ans = 0

for i in range(1,K+1):
  for j in range(1,K+1):
    ij = math.gcd(i, j)
    for k in range(1,K+1):
      ans += math.gcd(ij, k)

print(ans)

なんと、三つまとめて最大公約数を求めるのではなく、間で二つの最大公約数を求めた後、その値と残り一つの最大公約数を求めることで時間超過にならず、正解になります。
うーん、三つの最大公約数を求めるより、二つの最大公約数を2回求める方が、処理が早いのですかね？やってることは同じ気がするのですが、、、。