AtCoder Beginner Contest 162の感想

AtCoder

2020.04.122020.04.14

ABC162に参加した。

AtCoder Beginner Contest 162 - AtCoder

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – Lucky 7

1桁ずつ文字列として見ていく。

n = input()

flag = False
for s in n:
    if s == '7':
        flag = True
        break

print('Yes') if flag else print('No')

B – FizzBuzz Sum

全ての値のリストと、Fizz、Buzz、FizzBuzzに該当する値のリストを始めに作成する。

全ての値の合計値からFizzとBuzzを引き、重複して引き算してしまったFizzBuzzの値を加算する。

中学高校で習うド・モルガンの和集合の計算を思い浮かべるとイメージしやすい。

n = int(input())

total = [i for i in range(1, n + 1)]
fizz = [i for i in range(1, n + 1) if i % 3 == 0]
buzz = [i for i in range(1, n + 1) if i % 5 == 0]
fizzbuzz = [i for i in range(1, n + 1) if i % 15 == 0]

ans = sum(total) - sum(fizz) - sum(buzz) + sum(fizzbuzz)
print(ans)

C – Sum of gcd of Tuples (Easy)

全探索で実装。

3つ以上の最大公約数を求める関数は無いため、自分で関数をアレンジする必要がある。

高階関数のreduceは同じ処理を繰り返し行ってくれるので記述が楽。

内部的にはforで繰り返し行われているはずなので、場合によっては計算量には少し注意する必要がある。

import math
from functools import reduce

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 += reduce(math.gcd, [a, b, c])

print(ans)

D – RGB Triplets

全探索の解法しか思いつかず、O(N^3)では間に合わないと分かりつつ提出するもやはりTLE。

時間内に解けなかったため、コンテスト終了後に考察。

1つ目の条件は、RとGとBを1個ずつ選ぶ組み合わせの数と言い換えることが出来る。

そこから2つ目の条件に該当する場合を全探索で引き算すると答えを求めることが出来た。

n = int(input())
s = list(input())

r = sum([1 for x in s if x == 'R'])
g = sum([1 for x in s if x == 'G'])
b = sum([1 for x in s if x == 'B'])
ans = r * g * b

for i in range(n):
    for j in range(i + 1, n):
        k = 2 * j - i
        if j < k <= n - 1:
            if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                ans -= 1

print(ans)

茶色上位のレート600が見えてきた。