abc162

今回で4回目のコンテスト参加となりました。結果として、C問題まではなんとか解くことができました。ですが、B問題を1回凡ミスしたことに気づかず20分後に再提出したこととC問題はPythonでは時間制限を突破できなくて、PyPyで提出をしてなんとか正解だったのであまり良くない内容でした。 まだまだ余裕でD問題に到達することができていないです。。
基礎力を強化するためにも、今回も振り返りをしていきます。(回答に記載しているコードは提出してACしたコードです。)

A - Lucky 7

問題文

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

制約

  • 100 ≤ X ≤ 999

解説

この問題は入力された3桁の文字数それぞれに「7」が含まれているかを確認すればOKです。

回答

N = input()

if(N[0] == '7' or N[1] == '7' or N[2] == '7'):
    print("Yes")
else:
    print("No")

B - FizzBuzz Sum

問題文

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

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

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

制約

  • 1 ≤ X ≤ 10^6

解説

入力されたN項目までのそれぞれの数字をFizzBuzzで判別して、該当しない数字を足せばOKです。

回答

N = int(input())

ans = []
ans_num = 0
for i in range(N):
    s = i+1
    if(s%3 == 0 and s%5 == 0):
        ans.append("FizzBuzz")
    elif(s%3 == 0):
        ans.append("Buzz")
    elif(s%5 == 0):
        ans.append("Buzz")
    else:
        ans.append(s) 
        ans_num += s

print(ans_num)

C - Sum of gcd of Tuples (Easy)

問題文

$$ \sum_{a=1}^{K} \sum_{b=1}^{K} \sum_{c=1}^{K} gcd(a, b, c) $$ を求めてください。
ただし、gcd(a, b, c)はa,b,cの最大公約数を表します。

制約

  • 1 ≤ K ≤ 200 -　Kは整数

解説

Hugo製の本ブログではシグマなどの数式をいい感じで表示できないので、中央よせになってしまっています。（なんかいい方法ないかなあ。）
この問題は、math.gcdを使うことで最大公約数を求めることができます。math.gcdは3つ以上の入力に対応していないので、少し拡張しました。 最大公約数を求めることはすぐにできたのですが、Pythonで実行すると制限時間を超えてしまっていたのと、他の解き方がわからなかったので、 かなり時間を使ってしまいました。最終的にはPyPyで実行してこの問題を突破しました。

回答

PyPyで通ったコードを以下に記載します。

import math
from functools import reduce

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

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

print(ans)

PyPy3 (7.3.0)では実行時間が991msで、Python (3.8.2)では2205msと半分以下でした。PyPy速いですね。

D - RGB Triplets

問題文

‘R’, ‘G’, ‘B’のみからなる、長さNの文字列Sがあります。
以下の2つの条件をともに満たす組(i, j, k) (1 ≤ i < j < k ≤ N)の数を求めてください。

  • Si ≠ Sj かつ Si ≠ Sk かつ Sj ≠ Sk である
  • j−i ≠ k−j である

制約

  • 1 ≤ N ≤ 4000
  • Sは ‘R’, ‘G’, ‘B’のみからなる、長さNの文字列である

解説

この問題は解くことができませんでした。解法はABC162 解説を確認してください。 記載している回答はACしていた人を参考にさせていただいてます。

回答

N = int(input())
S = input()
R = []
G = []
B = []
for i in range(N):
    if S[i] == 'R':
        R.append(i)
    elif S[i] == 'G':
        G.append(i)
    elif S[i] == 'B':
        B.append(i)
ans = len(R)*len(G)*len(B)
for i in range(1,(N+1)//2):
    for j in range(i,N-i):
        if S[j] != S[j-i] and S[j] != S[j+i] and S[j-i] != S[j+i]:
            ans -= 1
print(ans)

おわりに

来週もABCコンテストがあるので、参加します！