[ABC302 Python]トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)A～D問題Python解説

A問題

A - Attack

# 入力
A, B = map(int, input().split())
# 割り切れる場合はA//B、割り切れない場合はA//B+1
if A%B == 0:
    print(A//B)
else:
    print(A//B + 1)

体力Aを攻撃Bで割った商が答えです。

B問題

B - Find snuke

# 入力
H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
# 横方向
for i in range(H):
    for j in range(W-4):
        # 左から右に"snuke"なら座標を出力
        if S[i][j] == "s" and S[i][j+1] == "n" and S[i][j+2] == "u" and S[i][j+3] == "k" and S[i][j+4] == "e":
            for k in range(5):
                print(i+1, j+1+k)
        # 右から左に"snuke"なら座標を出力
        elif S[i][j] == "e" and S[i][j+1] == "k" and S[i][j+2] == "u" and S[i][j+3] == "n" and S[i][j+4] == "s":
            for k in range(5):
                print(i+1, j+1+4-k)
# 縦方向
for i in range(H-4):
    for j in range(W):
        # 上から下に"snuke"なら座標を出力
        if S[i][j] == "s" and S[i+1][j] == "n" and S[i+2][j] == "u" and S[i+3][j] == "k" and S[i+4][j] == "e":
            for k in range(5):
                print(i+1+k, j+1)
        # 下から上に"snuke"なら座標を出力
        elif S[i][j] == "e" and S[i+1][j] == "k" and S[i+2][j] == "u" and S[i+3][j] == "n" and S[i+4][j] == "s":
            for k in range(5):
                print(i+1+4-k, j+1)
# 右下がり方向
for i in range(H-4):
    for j in range(W-4):
        # 左上から右下に"snuke"なら座標を出力
        if S[i][j] == "s" and S[i+1][j+1] == "n" and S[i+2][j+2] == "u" and S[i+3][j+3] == "k" and S[i+4][j+4] == "e":
            for k in range(5):
                print(i+1+k, j+1+k)
        # 左下から右上に"snuke"なら座標を出力
        elif S[i][j] == "e" and S[i+1][j+1] == "k" and S[i+2][j+2] == "u" and S[i+3][j+3] == "n" and S[i+4][j+4] == "s":
            for k in range(5):
                print(i+1+4-k, j+1+4-k)
# 右上がり方向
for i in range(H-4):
    for j in range(4,W):
        # 右上から左下に"snuke"なら座標を出力
        if S[i][j] == "s" and S[i+1][j-1] == "n" and S[i+2][j-2] == "u" and S[i+3][j-3] == "k" and S[i+4][j-4] == "e":
            for k in range(5):
                print(i+1+k, j+1-k)
        # 右下から左上に"snuke"なら座標を出力
        elif S[i][j] == "e" and S[i+1][j-1] == "k" and S[i+2][j-2] == "u" and S[i+3][j-3] == "n" and S[i+4][j-4] == "s":
            # print(i,j)
            for k in range(5):
                print(i+1+4-k, j+1-4+k)

縦、横、右下がり、右上がりそれぞれ2方向ずつ、
計8方向に"snuke”がないかを探します。
インデックスなので+1を忘れないでください。

C問題

C - Almost Equal

# インポート
from itertools import permutations
# 入力
N, M = map(int, input().split())
S = [list(input()) for _ in range(N)]

# 全順列
for i in permutations(S):
    # 条件を満たすかどうか
    judge = True
    # 文字列N個全て
    for j in range(N-1):
        # TiとTi+1の違う文字数
        c = 0
        for k in range(M):
            # 文字iが違えばcをカウントアップする
            if i[j][k] != i[j+1][k]:
                c += 1
        # 違う文字数が1以外の時は,条件を満たさない
        if c != 1:
            judge = False
            break
    # 条件を満たすような順列があればYesで出力する
    if judge:
        print("Yes")
        exit()
print("No")

制約が少ないので、並べ替えを全通り試すことができます。
並べ替えた文字列をすべて見ることで、何文字変更しなければいけないかをカウントすることができます。

D問題

D - Impartial Gift

# インポート
from bisect import bisect
# 入力
N, M, D = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
# Bを昇順に並べ替える
B.sort()
# 答え
ans = -1
# 全てのAについて
for a in A:
    # Bの中で、A+Dがどこにあるか調べる
    i = bisect(B, a+D) - 1
    # 2人への贈り物の価値の差がD以下ならansの最大値を更新する
    if i >= 0 and B[i] >= a - D:
        ans = max(ans, B[i]+a)
print(ans)

この問題の場合は全探索するとTLEになってしまうので、
調査範囲を狭める必要があります。
青木君を基準にすると、
青木君の贈り物Ai+Dが最大値となる可能性が高いです。
これを二分探索ですぬけ君の中から探し、
価値の差がD以下であることを確認し、価値の和を更新します。