[ABC430] ABC 430(Atcoder Beginner Contest)のA~C(A,B,C)問題をPythonで解説(復習)
A問題
- 法律は守ろう！！
A.py
"""
<方針>
- 法律は守ろう！！
"""
# 入力
A, B, C, D = map(int, input().split())
# A個以上持って、B個未満持つのは法律違反！
if(A<=C and B>D):
# 出力
print("Yes")
else:
print("No")
B問題
- 盤面をキーとして、集合
setに入れて行き、その長さを測ればよさそう。
B.py
"""
<方針>
- 盤面をキーとして、集合 `set` に入れて行き、その長さを測ればよさそう。
"""
# 入力
N, M = map(int, input().split())
SS = [input() for _ in range(N)]
# 集合
se = set()
# 盤面の左上を取得する
for i in range(N-M+1):
for j in range(N-M+1):
# キー
ke = ""
# 走査する
for k in range(M):
for l in range(M):
ke += SS[i+k][j+l]
# キーを追加する
se.add(ke)
# 出力
print(len(se))
C問題
方針
- 毎回区間を計算してたらとても間に合わない
O(N^2) - とりあえず、区間に含まれるものを
O(1)で取得できるように累積和を計算しておくO(N) - さて、左端を固定
O(N)して、右端を二分探索で当てはまる場所を探すO(logN) - 当てはまる場所を出すには、２回二分探索をする必要がある
- 全体として、
O(NlogN)で処理できる
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 毎回区間を計算してたらとても間に合わない `O(N^2)`
- とりあえず、区間に含まれるものを `O(1)` で取得できるように累積和を計算しておく `O(N)`
- さて、左端を固定 `O(N)` して、右端を二分探索で当てはまる場所を探す `O(logN)`
- 当てはまる場所を出すには、２回二分探索をする必要がある
- 全体として、`O(NlogN)` で処理できる
"""
# 入力
N, A, B = map(int, input().split())
S = input()
# 累積和
AA = [0]*(N+1)
BB = [0]*(N+1)
for i in range(N):
AA[i+1] = AA[i] + (1 if S[i] == 'a' else 0)
BB[i+1] = BB[i] + (1 if S[i] == 'b' else 0)
# 個数
ans = 0
# 左端を固定ループする
for i in range(N):
# Aの当てはまる場所を二分探索
l = i-1
r = N+1
while abs(l-r) > 1:
m = (l+r)//2
if(A <= (AA[m] - AA[i])):
r = m
else:
l = m
L = r
# 条件に当てはまる場所がない
if(L > N):
continue
# Bの当てはまる場所を二分探索
l = i-1
r = N+1
while abs(l-r) > 1:
m = (l+r)//2
if((BB[m] - BB[i]) < B):
l = m
else:
r = m
R = l
# 個数を増やす
ans += max(R-L+1, 0)
# 出力
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- 最近モチベが下がってて、Cまでしかやってない。これ続ける意味あるのか...？