ABC466のPython解答（A～E）

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

A問題

リストの最大値が0未満か確認

A

n = int(input())
a = list(map(int, input().split()))

print("Yes" if max(a) < 0 else "No")

B問題

色ごとに大きさを記録

B

n, m = map(int, input().split())

ball = [-1] * m
for _ in range(n):
    c_i, s_i = map(int, input().split())
    ball[c_i - 1] = max(ball[c_i - 1], s_i)

print(*ball)

C問題

$(i, j)$が1以下の時$(i+1,j),(i+2,j)$...も条件を満たすので重複して質問しないように気を付ける
あとは確定した組み合わせを確実に記録する

C

def check(a, b):
    print("?", a + 1, b + 1, flush=True)
    return input() == "Yes"

def update(x, y):
    global lst
    for i in range(x, y):
        lst[i][y] = True


n = int(input())

lst = [[False] * n for _ in range(n)]

for i in range(n):
    j = i + 1
    while j < n:
        if not lst[i][j]:
            flg = check(i, j)
            if flg:
                update(i, j)
            else:
                break
        j += 1

ans = sum(sum(l_i) for l_i in lst)
print("!", ans)

D問題

縦と横でそれぞれ状況を保持し、適切に更新する

D

n, m = map(int, input().split())

cro_row = dict()
cro_col = dict()

for _ in range(m):
    r_i, c_i = map(lambda x:int(x) - 1, input().split())

    if r_i in cro_row:
        for c_j in list(cro_row[r_i]):
            cro_col[c_j].discard(r_i)
    if c_i in cro_col:
        for r_j in list(cro_col[c_i]):
            cro_row[r_j].discard(c_i)

    cro_row[r_i] = {c_i}
    cro_col[c_i] = {r_i}

cross = sum(len(v_i) for v_i in cro_row.values())

print(cross)

E問題

DP

• 長い区間裏返したあと間を表に戻す
• 表に戻さず区間を裏にする
  上の２つは同じ回数裏返すため下だけで考える

$dp[i][j][k] = i$番目のカードの時点で$j$回裏返していてかつ$i$番目のカードが$k$[表, 裏]の時の最大スコア

E

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

INF = float("inf")
# i回目の時点で[j回裏返した][表のまま、裏返した]時の最大スコア
dp = [[-INF, -INF]for _ in range(k + 1)]
dp[0][0] = 0

for a_i, b_i in card:
    new_dp = [[-INF, -INF]for _ in range(k + 1)]
    for i in range(k + 1):
        if i == 0:
            new_dp[i][0] = dp[i][0] + a_i
        else:
            new_dp[i][0] = max(dp[i][0], dp[i][1]) + a_i
            new_dp[i][1] = max(dp[i - 1][0], dp[i][1]) + b_i
    dp = new_dp

print(max(max(dp_i) for dp_i in dp))