競プロ初心者の復習用記事です。
ここで書く解は解説や他の人の提出を見ながら書いたものです。自分が実際に提出したものとは限りません。
A - Lucky 7
与えられた3桁の数字が７のつく数字か答える問題です。
どう書いても通ると思いますが。文字列のまま扱い、inで存在チェックするのが一番きれいでしょうか。
S = input()
if '7' in S:
print('Yes')
else:
print('No')
B - FizzBuzz Sum
与えられた数字KまでFizzだったりBuzzだったりしない数字だけを数え、合計するといくつになるか答える問題です。
そのまま書いたら通りました。$N=10^6$での$O(n)$なら特別に効率化する必要はないですね。
count = 0
n = int(input())
for i in range(1, n+1):
if i%3 and i%5:
count += i
print(count)
C - Sum of gcd of Tuples (Easy)
K以下の三つの数字全てについて最大公約数を合計するといくつになるかを答える問題です。
全ての組み合わせをitertools.combinations_with_replacementで作成して最大公約数を求め、$a\neq b\neq c$ならその6倍、$a\neq b=c$とかならその3倍を足していく。一度計算した公約数は保存していって高速化しようとしました。
あんまりきれいな感じはしませんが、これで一応通りました。
import itertools
import math
K = int(input())
g = [[0] * (K+1) for _ in range(K+1)]
out = 0
for a, b, c in itertools.combinations_with_replacement(range(1, K+1), 3):
if g[a][b] == 0:
g[a][b] = math.gcd(a, b)
d = g[a][b]
if g[d][c] == 0:
g[d][c] = math.gcd(d, c)
if a == b and b == c:
out += g[d][c]
elif a != b and b != c:
out += g[d][c] * 6
else:
out += g[d][c] * 3
print(out)
D - RGB Triplets
RGBの三種類の組み合わせが何通り作れるか考える問題です。ただし一定条件下で組み合わせは弾かれます。
RGB全ての組み合わせは$Rの個数\times Gの個数\times Bの個数$だけあります。ここから条件にひっかかる組み合わせの数を引いていきます。
除外の条件である「一定距離ずつ離れた組み合わせ」というのは離れる距離と開始地点の二つをforで回して$O(n^2)$で取得できます。このインデックスがR, G, Bの三つを埋めているなら除外対象として含まれることになります。
というわけで、以下のようなコードを書きました。これで通りました。
import itertools
N = int(input())
S = input()
out = S.count('R') * S.count('G') * S.count('B')
RGBs = list(itertools.permutations(['R', 'G', 'B'], 3))
for i in range(1, N):
for j in range(N-i*2):
if (S[j], S[j+i], S[j+i*2]) in RGBs:
out -= 1
print(out)
E - Sum of gcd of Tuples (Hard)
再び最大公約数の問題ですが、先ほどの解き方では絶対に間に合わないほど値が増えています。
諦めました。解説を見ます。
$\gcd(a, b, c, ...)=X$を求める上で$a, b, c, ...$の全部の組み合わせを求める時間はないので、特定の$X$を満たす$a, b, c, ...$の組み合わせの数を数えていきます。
$a, b, c, ...$の最大公約数が$X$になるということは、「$a, b, c, ...$の全てが$X$で割れる」「$a, b, c, ...$の全てが$n\times X$(ただし$n>1$)では割れない」という二つの条件を満たしていることになります。
まず「$a, b, c, ...$の全てが$X$で割れる」の条件を考えてみましょう。Kから1までの数字の中で、Xの倍数であるものは$K\over X$個存在します。それがN個だけ並んでいるので、$a, b, c, ...$の組み合わせは$({K\over X})^N$個存在します。
さらに「$a, b, c, ...$の全てが$n\times X$(ただし$n>1$)では割れない」という条件は、Xの探索を高い順に行い、$2X, 3X, ...$の倍数であるものの組み合わせの数を順番に引いていけばよいです。
こうしてXとなる組み合わせの数がそれぞれ求まったので、それぞれの組み合わせの数×Xの値を合計すれば求まります。
というわけで、実装したものが以下になります。
N, K = map(int, input().split())
li = [0]*(K+1)
out = 0
mod = 10**9+7
for i in range(K, 0, -1):
li[i] = pow(K//i, N, mod)
for j in range(i*2, K+1, i):
li[i] -= li[j]
out += li[i] * i
print(out%mod)
この記事はここまでとします。