[ABC430] ABC 430(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)
合計回答時間：60分
A問題
自分の回答
かかった時間：10分
A, B, C, D = map(int, input().split())
if C >= A and D < B:
print("Yes")
else:
print("No")
終了後考えた最適な回答
A, B, C, D = map(int, input().split())
if C >= A and D < B:
print("Yes")
else:
print("No")
B問題
自分の回答
かかった時間：20分
# 3行3列からなるグリッド、#なら黒、.なら白
# 2行2列を取り出す方法はいくつある
N,M = map(int,input().split())
S = [list(input()) for _ in range(N)]
# resultというリストに組み合わせを保存する
results = []
for k in range(N-M+1):
for j in range(N-M+1):
result = []
for i in range(M):
result.append(S[i+k][j:j+M])
if result not in results:
results.append(result)
print(len(results))
終了後考えた最適な回答
# 重複をなくすためにsetが使える
N,M=map(int,input().split())
S=[input() for _ in range(N)]
grid_set=set()
for i in range(N-M+1):
for j in range(N-M+1):
grid = tuple(S[ii][j:j+M] for ii in range(i,i+M))
print(grid)
grid_set.add(grid)
print(len(grid_set))
C問題
自分の回答
累積和を使って求めるのだろうという予測が立てられたが、その後二分探索を使う必要があるところまではわからなかった
かかった時間：30分
# 4分以上運転するなら2分以上休憩を取る必要がある
# 長さ11の文字列
# 1<= l <= r <= 11
# Sのlからr文字目までに含まれるaの個数が4以上
# Sのlからr文字目までに含まれるbの個数がB未満
N,A,B = map(int,input().split())
S = list(input())
for i in range(N):
for j in range(N):
sum_A = S[i:j].count('a')
sum_B = S[i:j].count('b')
if sum_A >= A and sum_B < B:
print(i+1,j,S[i:j])
終了後考えた最適な回答
import bisect
N,A,B = map(int,input().split())
S = input()
sum_A = [0] * (N+1)
sum_B = [0] * (N+1)
for i in range(N):
sum_A[i+1] = sum_A[i] + (1 if S[i] == 'a' else 0)
sum_B[i+1] = sum_B[i] + (1 if S[i] == 'b' else 0)
print(sum_A)
print(sum_B)
ans = 0
for l in range(N):
r_a = bisect.bisect_left(sum_A, sum_A[l] + A)
r_b = bisect.bisect_left(sum_B, sum_B[l] + B)
print(l,r_a,r_b)
ans += max(r_b - r_a, 0)
print(ans)
次に向けてやること
・二分探索の問題を解く
・安定してテストを受けられる環境を用意
感想
やっぱり累積和の知識が必要な問題の出題率がC問題はかなり高い。二分探索を事前に勉強していれば今回の問題はとけたのかも