ABC416をPythonで（A～D）

AtCoder Beginner Contest 416の解答等の速報的まとめ

A問題

問題文の「すべてo」を「Xを含まない」に読み替える

A

n, l, r = map(int, input().split())
s = input()

print("No" if "x" in s[l-1:r] else "Yes")

B問題

ドットの場所で直前にoを書いていなければ書いてよい
oを書いた後#が来ていればそのあとのドットでoをかけるので、前から順番に判定してく

B

s = list(input())

dot = list()
flag = True
for i, s_i in enumerate(s):
    if s_i == "#":
        flag = True
    else:
        if flag:
            dot.append(i)
            flag = False

for d_i in dot:
    s[d_i] = "o"

print("".join(s))

C問題

dfsですべてのパターンを生成する

C

n, k, x = map(int, input().split())
s = [input() for _ in range(n)]

data = list()
lst = []
def dfs(ind):
    global data, lst
    if ind == k:
        data.append("".join(lst))
    else:
        for s_i in s:
            lst.append(s_i)
            dfs(ind + 1)
            lst.pop()

dfs(0)
data.sort()
print(data[x - 1])

D問題

$a_i + b_i < 2 \times m$なので$a_i+b_i >= m$となる組み合わせが最大何組作れるか調べて$sum(a)+sum(b)$から$m$を組数分引く

D

for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    a.sort()
    b.sort(reverse=True)
    ans = sum(a) + sum(b)
    ind = 0
    for a_i in a:
        if a_i + b[ind] >= m:
            ans -= m
            ind += 1

    print(ans)

Eの感想

空港連絡用の頂点airを別で作って$d_i$→air=t,air→$d_i$=0として設定し、ワーシャルフロイドで距離を計算する
辺を追加したときは影響を与える$4\times N^2$通りを更新する

解説通りの考察はできているけどWA吐いててどうにもならなかった