ABC 300 備忘録 #Python

概要

　今回はABC300（2023年4月30日21:00~22:40）のポイントと自分の実装について書いていこうと思う。

A問題

ポイント

選択肢の番号とリストの番号が1ずれていることに注意する
選択肢をリストとして受け取り、答えと同じ値であるかどうかを判断

自分の実装

ABC_300_A.py

N, A, B = map(int, input().split())

C = list(map(int, input().split()))

ans_sum = A + B

for i in range(N):
    if C[i] == ans_sum:
        print(i+1)
        exit()

B問題

ポイント

縦→横の変換である
縦横に動かした時のますの状態は元のマスに対して4方にマスを並行移動して繋げた際に始点をずらしたものに等しい

自分の実装

ABC_300_B.py

H, W = map(int, input().split())

A = list(list(input()) for i in range(H))

B = list(list(input()) for i in range(H))

A_rev = []

for num in range(2):
    for i in range(H):
        A_rev_i = A[i]
        for j in range(W):
            A_rev_i.append(A[i][j])
        A_rev.append(A_rev_i)

for i in range(H):
    for j in range(W):
        A_rev_new = [x[j:j+W] for x in A_rev[i:i+H]]
        if A_rev_new == B:
            print('Yes')
            exit()

print('No')

C問題

ポイント

中心の点から斜め方向に伸ばした際の4隅が # となっているかどうかを判定
判定で条件に合わない時点でループをbreakし、バツ印のサイズを確定

自分の実装

ABC_300_C.py

H, W = map(int, input().split())

C = list(list(input()) for i in range(H))

N = min(H, W)

S = [0 for i in range(N+1)]

# 中心のマーク探し
for i in range(1,H-1):
    for j in range(1,W-1):
        # 条件を満たさない場合は次の候補へ
        if C[i][j] != '#':
            continue
        # 角のグリッドが#となるので、グリッドの範囲内に収まるように設定
        n = min(i,H-1-i,j, W-1-j)
        size = 0
        for k in range(1, n+1):
            if C[i + k][j + k] == '#' and C[i + k][j - k] == '#' and C[i - k][j + k] == '#' and C[i - k][j - k] == '#':
                size += 1
            else:
                break
        S[size] += 1
        
print(*S[1:])

D問題

ポイント

相異なる素数の積の場合、$10^{12}$までの積ならば、高々考えるべき素数は$10^6$まで
３つの素数のうち最大であるcの範囲をa, bにより上限の範囲を絞ることが可能である（これはコンテスト中に気づくことができなかった）

自分の実装

　この実装だとTLEになってしまった

ABC_300_D.py

import math

# 素数 s を探す関数
def search_simple_number(num):
    simple_number = [2]
    for s in range(3, num):
        div_num = 0
        sqrt_s = int(math.sqrt(s))
        for div in range(2, sqrt_s + 1):
            if s % div == 0:
                div_num += 1
                break
        if div_num == 0:
            simple_number.append(s)
    return simple_number, len(simple_number)
        
N = int(input())

simple_number_list, length = search_simple_number(N)

if length <= 2:
    print(0)
    exit()

ans = 0
    
for i in range(length-2):
    for j in range(i+1, length-1):
        for k in range(j+1, length):
            a_square = simple_number_list[i] ** 2
            b = simple_number_list[j]
            c_square = simple_number_list[k] ** 2
            multi = a_square * b * c_square
            if multi <= N:
                ans += 1
            else:
                continue
print(ans)

感想

　今回はC問題まで自分としてはすんなりと解くことができた。D問題に関しては数学的な考察が足りなかったと感じている。後日やり直したい。