AtCoder Beginner Contest 187の感想

ABC187に参加した。

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

A – Large Digits

やるだけ。

a, b = input().split()

a = sum(map(int, list(a)))
b = sum(map(int, list(b)))

ans = max(a, b)
print(ans)

B – Gentle Pairs

傾きの定義通りに計算するだけ。

ゼロ除算になる可能性があったので、今思えばWAを踏む可能性がある危ないコードだった。

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

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        x1, y1 = xy[i]
        x2, y2 = xy[j]

        grad = (y2 - y1) / (x2 - x1)
        if -1 <= grad <= 1:
            ans += 1

print(ans)

C – 1-SAT

重複を排除してくれるsetを使い、!ありと!なしの2グループ作り、共通要素があるかどうかを判定する。

n = int(input())

a = set()
b = set()
for _ in range(n):
    s = input()
    if s[0] == '!':
        a.add(s[1:])
    else:
        b.add(s)

ans = a & b
print('satisfiable') if ans == set() else print(list(ans)[0])

D – Choose Me

a+bが大きい順にソートし、a+bが同値を取る場合はaの大きい順に並び替える。

最初はこの方針で以下のコードを提出したが、WAが少しのこりAC出来なかった。

n = int(input())
x = []

aoki = 0
takahashi = 0

for _ in range(n):
    a, b = map(int, input().split())
    x.append([a, b, a + b])
    aoki += a

x.sort(key=lambda x: (x[2], x[0]), reverse=True)

ans = 0
for a, b, total in x:
    if aoki < takahashi:
        break

    aoki -= a
    takahashi += total
    ans += 1

print(ans)

演説により敵陣営とa+a+bの差ができるため、a+a+bをkeyとしてsortし、値の大きい箇所から演説して回ればOK。

n = int(input())
x = []

aoki = 0
takahashi = 0

for _ in range(n):
    a, b = map(int, input().split())
    x.append([a, b, a + a + b])
    aoki += a

x.sort(key=lambda x: (x[2]), reverse=True)

ans = 0
for a, b, _ in x:
    if aoki < takahashi:
        break

    aoki -= a
    takahashi += a + b
    ans += 1

print(ans)

緑が遠い……。