ABCD4完の緑パフォでした。以下振り返りと反省。

（2020年4月13日　D問題別解追記）

A - Lucky 7

問題のリンク

概要

3桁の整数 $N$ が与えられる。
$N$ のいずれかの桁に7が含まれるか否か。

制約

$100 ≤ N ≤ 999$
入力は全て整数

考察

特になし

コード

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

B - FizzBuzz Sum

問題のリンク

概要

$1$ から $N$ までの整数で、 $3$ でも $5$ でも割り切れない数を足し合わせる。

制約

$1 ≤ N ≤ 10 ^{6}$

考察

めちゃくちゃFizzBuzzでした。プログラマーなら誰しもが書いてきたもの。

コード

N = int(input())
ans = 0
for i in range(1, N+1):
    if i%3 != 0 and i%5 != 0:
        ans += i

print(ans)

C - Sum of gcd of Tuples (Easy)

問題のリンク

概要

- $\displaystyle{\sum_{a=1}^K}$ $\displaystyle{\sum_{b=1}^K}$ $\displaystyle{\sum_{c=1}^K}$ $gcd(a, b, c)$ を求めよ

制約

$1 ≤ K ≤ 200$

考察

制約を見るからに $a, b, c$ を全てfor文で探索すると[tex: o(N³)]で間に合わなそう。
なので少し工夫をして探索数を減らすことに具体的にはpermutation（順列）ではなく、combinations_with_replacement（重複あり組み合わせ）でgcdを求めて行くことに。それで書いたのが以下のような感じ。

コード

from itertools import combinations_with_replacement

from math import gcd   # gcd(6, 4) -> 2
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd, numbers)


N = int(input())
ans = 0
for i, j, k in combinations_with_replacement(range(1, N+1), 3):
    if i==j==k:
        ans += i
    elif i==j:
        ans += gcd(i, k)*3
    elif j==k:
        ans += gcd(j, i)*3
    elif i==k:
        ans += gcd(i, j)*3
    else:
        ans += gcd_list([i, j, k])*6
print(ans)

学び

ちなみに最初は上のコードのmathをfractionsにして出したところ普通にTLEでした。。。見た感じギリギリっぽかったのと他に良い案が思い浮かばなかったため、mathに変えたところ普通に通りました。。。時間はロスしたものの、手持ちのスニペットが少し整備されたのでそこは良かった。

D - RGB Triplets

問題のリンク

概要

R, G, Bからなる長さ $N$ の文字列 $S$ で、以下の条件を満たす $(i, j, k)$ の組みを求めよ。
$1 ≤ i \lt j \lt k ≤ N$
$S_i ≠ S_j$ かつ $S_j≠ S_k$ かつ $S_k ≠ S_i$
$j-i ≠k-j$

制約

$1 ≤ N ≤ 4000$

考察

これも全探索だと $O(N^3)$ でキツそう
iとjだけの探索なら、 $O(N^2)$ で行けるはず
予め、jの右側にRGBがそれぞれどれだけ存在しているかが分かれば、あとは指定の文字を一々数えなくても自ずと答えはわかる。（累積和を使うことで3つ目のfor文を無くせる。）
例えばi = 'R'、j='G'、であれば、jの左側にどれだけBがいくつ存在するかを見れば良い。
$j-i ≠k-j$ の制約だけ注意。もしこれに該当した場合、上記の値から $-1$

コード

N = int(input())
S = list(input())

num_r = S.count('R')
num_g = S.count('G')
num_b = N - num_r - num_g
C = [[num_r, num_g, num_b] for _ in range(N)]
r_cnt, g_cnt, b_cnt = 0, 0, 0

for i in range(N):
    if S[i] == 'R':
        r_cnt += 1
    elif S[i] == 'G':
        g_cnt += 1
    else:
        b_cnt += 1

    C[i][0] -= r_cnt
    C[i][1] -= g_cnt
    C[i][2] -= b_cnt

ans = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        if S[i] != S[j]:
            if 'R' not in [S[i], S[j]]:
                ans += C[j][0]
                if j+(j-i) < N and S[j+(j-i)]=='R':
                    ans -= 1
            if 'G' not in [S[i], S[j]]:
                ans += C[j][1]
                if j+(j-i) < N and S[j+(j-i)]=='G':
                    ans -= 1
            if 'B' not in [S[i], S[j]]:
                ans += C[j][2]
                if j+(j-i) < N and S[j+(j-i)]=='B':
                    ans -= 1

print(ans)

PyPyで通りました（457ms）。あとで順位表を見てみたところ、このD問題を早く解けるかどうかでだいぶパフォーマンスが違っていたようです。少し実装が複雑になってきたときに素早くバグなく書けるかどうか。。。力の無さを実感します。。。時間出てきたときに後半の問題も追記していきたいと思います。

（2020年4月13日　別解追記） PDF解答をみてなるほどと思ったので、実際にコーディング実装してみました。前のコードに比べるとかなり簡潔に書けてます。ポイントは以下の2点。

$S$ からR G Bの3つのを選ぶ方法はS.count('R') * S.count('G') S.count('B')通り。
制約 $j-i ≠k-j$ を考慮し、この条件に当てはる分を上記の値から引く。iとjをカウンターループさせるので $O(N^2)$

N = int(input())
S = input()

n_R = S.count('R')
n_G = S.count('G')
n_B = N - n_R - n_G
ans = n_R * n_G * n_B

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

print(ans)

解答見たあとだと、簡単にコーディングもできました。なるほどです。

Techブログ

AtCoder ABC 162

A - Lucky 7

概要

制約

考察

コード

B - FizzBuzz Sum

概要

制約

考察

コード

C - Sum of gcd of Tuples (Easy)

概要

制約

考察

コード

学び

D - RGB Triplets

概要

制約

考察

コード