AtCoderをPythonで取り組んだ振り返り(ABC430 A~B)

どうもこんにちは！

今週のコンテストはBまで完答、振り返りもBまで。
Cは累積和と尺取り法を使うとして、条件を満たしていたら次の文字も含んで問題なければ長くしてダメなら短くする、条件を満たさないときにbが多いなら条件を満たすまで短くする、aが少ないなら長くするみたいな処理でいけると思ったんですがWAとなりタイムアップ。考え方が違うのか実装がおかしいだけなのか。残念。
間違っているので折り畳みで一応。

C問題の途中まで(もし間違いを修正できたら正式にまとめて追記します・・・)

n,a,b = map(int,input().split())
s = list(input())

psum_a, psum_b = [0],[0]
for i in range(n):
    if s[i] == 'a':
        psum_a.append(psum_a[i]+1)
        psum_b.append(psum_b[i])
    else:
        psum_a.append(psum_a[i])
        psum_b.append(psum_b[i]+1)

ans = 0
l,r = 0,a+b-1 # lからr-1までの各文字の個数のインデックス
while r <= n:
    if l == r:
        r += 1
    elif psum_a[r] - psum_a[l] >= a and psum_b[r] - psum_b[l] < b:
        ans += 1
        if r < n and (s[r] == 'a' or (s[r] == 'b' and psum_b[r+1] - psum_b[l] < b)):
            r += 1
        else:
            l += 1
    elif psum_b[r] - psum_b[l] >= b: # bが多い場合は減るまで長さを削る
        while psum_b[r] - psum_b[l] >= b:
            l += 1
    else: # aが少ない場合は文字列を長くする
        while r <= n and psum_a[r] - psum_a[l] < a:
            r += 1

print(ans)

問題と公式の解説のリンク

問題は以下のリンクから。

A - Candy Cookie Law -

問題

a,b,c,dの整数が与えられ、c >= a かつ d < bを満たすかを判定する問題。

考え方とコード

if文を使って判定しました。

a,b,c,d = map(int,input().split())
if c >= a and d < b:
    print("Yes")
else:
    print("No")

B - Count Subgrid -

問題

整数NとM、さらにN × N行列のグリッドが与えられます。このグリッドからM × M行列のマスを抜き取るとったときに何種類あるかを回答する問題。なお1 < M < n <= 10です。

考え方とコード

愚直に全探索でM × Mで取り出したものをリストに入れて、種類を出力しました。

n,m = map(int,input().split())
grid = []
for _ in range(n):
    tmp  = list(input())
    grid.append(tmp)

ans = []
for i in range(n-m+1):
    for j in range(n-m+1):
        tmp = []
        for k in range(m):
            tmp.append(grid[i+k][j:j+m])

        if tmp not in ans:
            ans.append(tmp)
print(len(ans))

ではでは。