[ABC312 A~D Python]ユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)

A問題

A - Chord

# 入力
S = input()
# Sがいずれかと等しいときYes
if S in ["ACE", "BDF", "CEG", "DFA", "EGB", "FAC", "GBD"]:
    print("Yes")
else:
    print("No")

Sの候補が問題文に記載されていますので、
その中にあるかどうかで判断できます。

B問題

B - TaK Code

# 入力N,M
N, M = map(int, input().split())
# 入力S
S = [list(input()) for _ in range(N)]
# 条件を満たす箇所を保存するリスト
ans = []
# マス目をたどって条件を満たすマス目を探す
for i in range(N-8):
    for j in range(M-8):
            if (S[i][j] == "#" and
                S[i+1][j] == "#" and
                S[i+2][j] == "#" and
                S[i][j+1] == "#" and
                S[i][j+2] == "#" and
                S[i+1][j+1] == "#" and
                S[i+2][j+1] == "#" and
                S[i+1][j+2] == "#" and
                S[i+2][j+2] == "#" and

                S[i+6][j+6] == "#" and
                S[i+7][j+6] == "#" and
                S[i+8][j+6] == "#" and
                S[i+6][j+7] == "#" and
                S[i+6][j+8] == "#" and
                S[i+7][j+7] == "#" and
                S[i+8][j+7] == "#" and
                S[i+7][j+8] == "#" and
                S[i+8][j+8] == "#" and

                S[i+3][j] == "." and
                S[i+3][j+1] == "." and
                S[i+3][j+2] == "." and
                S[i+3][j+3] == "." and
                S[i][j+3] == "." and
                S[i+1][j+3] == "." and
                S[i+2][j+3] == "." and

                S[i+5][j+5] == "." and
                S[i+6][j+5] == "." and
                S[i+7][j+5] == "." and
                S[i+8][j+5] == "." and
                S[i+5][j+6] == "." and
                S[i+5][j+7] == "." and
                S[i+5][j+8] == "." ):
                ans.append([i+1,j+1])
# 一応ソートする
ans.sort()
for _ in ans:
    print(*ans)

出力例１に記載されている

###.?????
###.?????
###.?????
....?????
?????????
?????....
?????.###
?????.###
?????.###

を満たせば、TaK Codeを満たしているということになります。
めんどくさいですが、1マスずつ見ていくことで回答できます。

C問題

C - Invisible Hand

# インポート
import bisect

# 入力
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# 二分探索するためのソート
A.sort()
B.sort()
# 答えを用意
ans = 10**10
# N人について
for i in range(N):
    # 何人がりんごを売っていいと考えているか
    a = bisect.bisect(A, A[i])
    # 何人がりんごを買いたくないと考えているか
    b = bisect.bisect_left(B, A[i])
    # 売っていい人が買いたい人以上だったら、ansを更新
    if a >= M-b:
        ans = min(ans, A[i])
# M人についても同様
for i in range(M):
    a = bisect.bisect(A, B[i]+1)
    b = bisect.bisect_left(B, B[i]+1)
    if a >= M-b:
        ans = min(ans, B[i]+1)

print(ans)



        

二分探索を用います。
条件を満たすためには、
売り手の人数をできるだけ多く、買い手の人数をできるだけ少なくできるようにします。
よって、AiとBi+1を全部調べれば、
その中に答えがあります。

D問題

D - Count Bracket Sequences

# 入力
S = input()
# 割った余り
MOD = 998244353
# dp[i][j]:i文字目の時に、"(の個数-)の個数=j"となる個数
dp = [[0]*(len(S)+1) for _ in range(len(S)+1)]
# 最初は"(の個数-)の個数=0"になる
dp[0][0] = 1
# 全ての文字について
for i in range(len(S)):
    # "(の個数-)の個数=j"となる可能性
    for j in range(len(S)):
        # S[i]が"("または"?"の時、
        # S[i]は"("にすることができるので、
        # j+1を更新する
        if S[i] == "(" or S[i] == "?":
            dp[i+1][j+1] += dp[i][j]
            dp[i+1][j+1] %= MOD
        # S[i]が")"または"?"の時、
        # S[i]は")"にすることができるので、
        # j-1を更新する
        if S[i] == ")" or S[i] == "?":
            if j > 0:
                dp[i+1][j-1] += dp[i][j]
                dp[i+1][j-1] %= MOD
# 括弧列となるのは、
# "(の個数-)の個数=0"の時
print(dp[len(S)][0])

2023/08/01追記しました。

動的計画法で解いていきます。
よく出る問題の形式なので、解法を覚えてしまう方が早いと思います。

括弧列となる条件は以下の2つです。
①全てのiについて、S[i]までに含まれる「"("の数>")"の数」
②Sに含まれる「"("の数=")"の数」

この2つの条件を満たすようにDPを見ていく必要があります。
"("の数と")"の数の差を保存しておくことで、
解答はSをすべて見終わったときの「"("の数=")"の数」の数になります。