[ABC381] ABC 381(Atcoder Beginner Contest)のA~D(A,B,C,D)問題をPythonで解説(復習)
A問題
- 左側
leftが全部1 - 真ん中
midが/ - 右側
rightが全部2 -
//は切り捨てに注意．
A.py
"""
<方針>
- 左側`left`が全部`1`
- 真ん中`mid`が`/`
- 右側`right`が全部`2`
- `//`は切り捨てに注意．
"""
# 入力
N = int(input())
S = input()
left = S[:N//2] # 左側
mid = S[N//2] # 真ん中
right = S[N//2 + 1:] # 右側
# 全ての条件が一致する時
if(
left == "1"*(N//2) and
mid == "/" and
right == "2"*(N//2)
):
# Yes
print("Yes")
else:
# No
print("No")
B問題
- 文字の長さが奇数ならすぐ
Noを出力する． - 文字を二つずつみて，同じかどうかをみる．既にみたことある英小文字かどうかも確認する．
B.py
"""
<方針>
- 文字の長さが奇数ならすぐ `No` を出力する．
- 文字を二つずつみて，同じかどうかをみる．既にみたことある英小文字かどうかも確認する．
"""
# 入力
S = input()
# 入力文字列が奇数の時
if(len(S)%2==1):
# Noとして，プログラムを終了する．
print("No")
exit()
# 既にみたことあるかどうかを管理するリスト
look = [False]*26
# 2文字ずつ見る
for i in range(len(S)//2):
# 連続する2文字が等しい時，
if(S[i*2]==S[i*2 + 1]):
# リスト上での現在の文字のindex
ind = ord(S[i*2]) - ord("a")
# 既にみたことある文字なら
if(look[ind]):
# Noとして，プログラムを終了する．
print("No")
exit()
# 既にみたことあるものとして登録する．
look[ind] = True
# 連続する2文字が等しく無い時，
else:
# Noとして，プログラムを終了する．
print("No")
exit()
# Yesを出力
print("Yes")
C問題
方針
- 番兵として右側に
1を置いておく． - 左側から見る．
-
1がどれだけ連続するかを記録する． -
/が出てきたら2の数を数える． - 条件分岐を頑張って実装する．ソースコードは
†WYSIWYG†です． - P.S.
- 左から順番に見ていくだけなので，計算量は
O(N)です．
- 左から順番に見ていくだけなので，計算量は
前提
-
C問題あたりで，TLEになる人は，制約条件を見る癖をつけよう． -
AとB問題では，基本的に制約条件を見ずにやっても解ける． - しかし，
C問題以降では，制約条件を見ないと必ずTLEすると思っても良い． - 詳しい話は私の352回の記事 の
C問題の解説に記したので，是非参照してほしい．
C.py
"""
<方針>
- 番兵として右側に `1` を置いておく．
- 左側から見る．
- `1` がどれだけ連続するかを記録する．
- `/` が出てきたら `2` の数を数える．
- 条件分岐を頑張って実装する．ソースコードは `†WYSIWYG†` です．
"""
# 入力
N = int(input())
S = list(input())
# 番兵
S.append("1")
ans = -1 # 答え
look = 1 # 現在何をカウントアップしているか．最初は1
one = 0 # 1の現在のカウント数
two = 0 # 2の現在のカウント数
# 文字を順番に見ていく．
for s in S:
match look:
case 1:
match s:
case "1":
one += 1
two = 0
look = 1
case "/":
two = 0
look = 2
case "2":
one = 0
two = 0
look = 1
case 2:
match s:
case "1":
ans = max(ans, min(one, two)*2 + 1) # 答えを更新
one = 1
two = 0
look = 1
case "/":
ans = max(ans, min(one, two)*2 + 1) # 答えを更新
one = 0
two = 0
look = 1
case "2":
two += 1
look = 2
# 出力
print(ans)
D問題
- 尺取法で左から順番に見ていく．
- 常に長さ
lを意識して処理する． - そのまま
Aを二つずつ調べるか，最初の一個を飛ばして調べるかの2通りやる必要がある．
D.py
"""
<方針>
- 尺取法で左から順番に見ていく．
- 常に長さ `l` を意識して処理する．
- そのまま `A` を二つずつ調べるか，最初の一個を飛ばして調べるかの2通りやる必要がある．
"""
N = int(input())
A = list(map(int, input().split()))
def check(A):
# 特定の数値が出てきた時のindexを管理
di = {}
# 現在の長さ(2個で1つの長さ．ansでは2倍すれば良い．)
l = 0
# 答え
ans = 0
# セットずつ見ていく
for i in range(len(A)//2):
# セットが合った時
if A[2*i] == A[2*i + 1]:
a = A[2*i]
# 既にその数値が組み込まれている時，
if a in di:
# その長さを組み込んだ長さ or 同一の文字を削除した長さ
l = min(l + 1, i - di[a])
# まだ組み込まれてない時，
else:
# 組み込んだ長さ
l += 1
di[a] = i
# セットが合わなかった時
else:
# 長さをリセット
l = 0
# indexもリセット
di = {}
# 答えを更新
ans = max(ans, 2*l)
return ans
# 部分列全体と部分列 A[1:] の両方を調べる
ans = max(check(A), check(A[1:]))
print(ans)
補足
関係するリンク(参考文献など)
筆者について
- Atcoderアカウント
- 今回も不参加のため，成績なし．
- 解説で示したA問題の提出
- 解説で示したB問題の提出
- 解説で示したC問題の提出
- 解説で示したD問題の提出
その他
- 間違いを含んでいる可能性があります．
- 方針と言いつつ，方針ではない感想などを書いている可能性があります．
- A問題から解説がだんだん省略されます．
- コードに書かれている解説の文言と，その上に書いてある解説の文言を変えている場合があります．
最後に一言
- そろそろ本気出すか...❤️