AtCoder ABC162

AtCoder ABC162解いた分だけまとめ。
今回はAB2完。CでTLEになってしまって爆死。
全探索かなーと思ってitertools.productを使ったのが悪く、単純に3重ループで解けた。
なんだかとても悲しい。
でも、言語アップデートがされて、gcdする時にmathがちゃんと使えるのは嬉しかった。

ちょうどAtCoder Problems BootCampができたそうなので、
これをおとなしく解いて素直に実装する練習をしようと思った...がんばるぞ

目次

• A問題
• B問題
• C問題

A. Lucky 7

問題文

数字を文字列として受け取り、各桁に7がいたらYesを出して強制終了、
何もなければ普通にNoを出す。
最近この手の問題(文字列の各文字を検証する)多いなぁ

ACしたコード

#coding:utf-8
n = input()

for i in range(3):
    if n[i] == '7':
        print('Yes')
        exit()

print('No')

B. FizzBuzz Sum

問題文

みんなだいすきFizzBuzz。
ただし、FizzBuzz列の数字の和だけほしいと言われているので、
FizzとかBuzzとかFizzBuzzとしないといけないところは0で置換し、
最後に和を求めればOK

ACしたコード

#coding:utf-8
n = int(input())
num = []
for i in range(1, n+1):
    if i % 3 == 0 or i % 5 == 0:
        num.append(0)
    else:
        num.append(i)

#print(num)
print(sum(num))

C. Sum of gcd of Tuples (Easy)

問題文

今回メンタルがしんだ原因。素直に実装することを忘れた気がする。
パターンを全部書きだして、gcdして和を求める問題。
結論から言えば、3重ループしながらgcdする組み合わせを出して、
2つずつgcdすればギリギリTLEすることなく答えが出た。

解説ACしたコード

#coding:utf-8
from math import gcd

def main():
    k = int(input())
    ans = 0

    for a in range(1, k+1):
        for b in range(1, k+1):
            for c in range(1, k+1):
                ans += gcd(gcd(a, b), c)

    print(ans)

if __name__ == "__main__":
    main()

ここからTLEした話。ちなみにPyPyでもアウト。
gcdを一気に3つの数で出そうとして、高階関数を使う。
そして、全組み合わせを求めるのに、itertools.productで直積を求めることで実現。
後で調べてわかったけれど、どうもitertools.productは遅いらしい。

激遅

ポイント

とはいえ、学んだことはあるのでメモ。

1. 直積は、 itertools.productを使う
ただし、出力はtupleになる。

2. 畳み込み演算をする時にはfunctools.reduceを使う
リストやタプルの要素の足し合わせや減算が可能。今回はこれを使って再帰的に3つの数のgcdを求めた。

TLEしたコード

#coding:utf-8
import math
import itertools
from functools import reduce

def gcd(num):
    return reduce(math.gcd, num)

def main():
    k = int(input())
    ans = 0

    num = [i for i in range(1,k+1)]
    comb = tuple(itertools.product(num, repeat=3))


    for i in comb:
        ans += gcd(i)

    print(ans)

if __name__ == "__main__":
    main()

参考

note.nkmk.me

www.lifewithpython.com