AtCoder ABC466振り返り (PythonでABC問題)

ABC466を振り返ります

今回はABまで2問解答でした。
C問題が出題頻度低いインタラクティブ問題で、かつ尺取り法をすっかり忘れていたので解けませんでした。

A - Compromise

全探索をして、x >= 0 の項目があるかどうかをチェックしました。

N = int(input())
X = list(map(int, input().split()))

exist = False
for x in X:
    if x >= 0:
        exist = True
        break

if exist:
    print("No")
else:
    print("Yes")

B - Representative Balls

ボールの色と大きさの関連を (defaultdict) ball[color] = size で保持するようにしました。

N, M = map(int, input().split())
ball = defaultdict(int)
for i in range(N):
    C, S = map(int, input().split())
    ball[C] = max(ball[C], S)

answers = []
for k in range(1, M+1):
    if k in ball:
        answers.append(ball[k])
    else:
        answers.append(-1)

print(*answers)

C - Count Close Pairs

尺取り法を覚えていなくて、結局バグが取れず敗北...。
ソースコードはコンテスト後に書いたものです。

N = int(input())

# indexに対して、どこまでが条件内なのか
max_r = [0] * (N + 10) 

# 探索の初期位置
left = 1
right = 2

while left < N:
    print("?", left, right)
    response = input()

    if response == "Yes":
        # 左側 left に対して、rightまでは条件内
        max_r[left] = right

        # 右側 を1つ進める
        right += 1
        if right > N:
            left = left + 1
            right = N
    else:
        # 左側 left に対して、right-1までは条件内
        max_r[left] = max(max_r[left], right - 1)

        # 左側 をひとつ進める
        left = left + 1
        if left == right:
            right = left + 1
            if right > N:
                break

answer = 0
for i in range(N):
    if max_r[i] != 0:
        answer += max_r[i] - i
print("!", answer)
exit()