AtCoder Beginner Contest 162 過去問

Python AtCoder

悲報

ここ最近勉強をサボっていたツケですね・・・
これからは毎日AtCoderの問題解きますので、
AtCoderの神様・・・どうか私を見捨てないで・・・

A問題

これは楽勝。

n = input()
if '7' in n: print('Yes')
else: print('No')

B問題

FizzBuzz問題を若干いじったものでした。

n = int(input())+1
i,sum = 1,0
while i<n:
  if i%3!=0 and i%5!=0: sum+=i
  i+=1
print(sum)

C問題

itertoolsを使って、順列&重複
hibiki-press.tech
イテレータを生成しました。
これに最大公約数を求めます。

import numpy as np
import math
import itertools
nums = np.arange(1,int(input())+1)
pp = list(itertools.product(nums, repeat=3))
sum = 0
for p in pp:
  k=math.gcd(p[0],p[1])
  sum+=math.gcd(k,p[2])
print(sum)

しかしTLE。

  • 3つ異なる数字で構成(A)
  • 2つの数字で構成(B)
  • 全て1つの数字で構成(C)

に分類し、計算量の無駄を省きます。

Cでは1~Nまでの合計を足すだけなので、
わざわざ最大公約数を求める必要はありません。

Bでも(1,1,2)(2,1,1)(1,2,1)(2,1,2)(1,2,2),(2,2,1)を(1,2)で表現して、
あとで6倍すれば同義です。

import math
import itertools
n = range(1,int(input())+1)
ppp = list(itertools.combinations(n, 3))
pp = list(itertools.combinations(n, 2))
asum,bsum,csum = 0,0,0
for p in ppp:
  asum+=math.gcd(math.gcd(p[0],p[1]),p[2])
for p in pp:
  bsum+=math.gcd(p[0],p[1])
for p in n:
  csum+=p
 
print(asum*6+bsum*6+csum)