AtCoder Beginner Contest 181 Participation Report

AtCoder Beginner Contest 181 Participation Report

ABC181A - Heavy Rotation

Break through in 1 minute. Just write.

N = int(input())

if N % 2 == 0:
    print('White')
else:
    print('Black')

ABC181B - Trapezoid Sum

Break through in 4 minutes. It took a long time to change the formula to subtract the total from A to A-1 because the formula to calculate the total from A to B did not come out.

N = int(input())

result = 0
for _ in range(N):
    A, B = map(int, input().split())
    result += B * (B + 1) // 2
    result -= (A - 1) * A // 2
print(result)

When I calmed down, the ceremony came out properly (laughs).

N = int(input())

result = 0
for _ in range(N):
    A, B = map(int, input().split())
    result += (A + B) * (B - A + 1) // 2
print(result)

ABC181C - Collinearity

Break through in 19 minutes. Start by google the formula of the straight line passing through the two points. N ≤ 10 2 </ sup> So * O * (* N * 3 </ sup>) is OK It took me a while to notice. In the input / output example, division by zero came out and I remember the x = a type straight line (laughs). Although the formula was slightly wrong, I was lucky enough to be picked up in the input / output example. Can be fixed, no mistakes AC.

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

for i in range(N - 1):
    xi, yi = xy[i]
    for j in range(i + 1, N):
        xj, yj = xy[j]
        for k in range(j + 1, N):
            x, y = xy[k]
            if xj == xi:
                if x == xi:
                    print('Yes')
                    exit()
            elif yj == yi:
                if y == yi:
                    print('Yes')
                    exit()
            elif abs(y - (yj - yi) / (xj - xi) * (x - xi) - yi) < 0.000001:
                print('Yes')
                exit()
print('No')

Addendum: If you multiply both sides by the division term, you can calculate accurately with an integer, and there was no division by zero ...

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

for i in range(2, N):
    xi, yi = xy[i]
    for j in range(1, i):
        xj, yj = xy[j]
        for k in range(j):
            x, y = xy[k]
            if (y - yi) * (xj - xi) == (yj - yi) * (x - xi):
                print('Yes')
                exit()
print('No')

ABC181D - Takahashi Unevolved

It breaks through in 13 and a half minutes. If you notice that digits over 1000 are automatically multiples of 8, it's a problem that ends immediately. So, I was able to AC with the code below, but there seems to be a bug. 3 digits At the above time, I didn't use '008' or '016' as a tree, and I thought that it might be a check for a pattern in which the characters left over in 4 digits are 0. ,safe.

from collections import Counter

S = input()

if len(S) == 1:
    if S == '8':
        print('Yes')
    else:
        print('No')
elif len(S) == 2:
    if ''.join(sorted(S)) in ['16', '24', '23', '04', '48', '56', '46', '27', '08', '88', '69']:
        print('Yes')
    else:
        print('No')
else:
    c = Counter(S)
    for x in range(104, 1000, 8):
        d = Counter(str(x))
        for k in d:
            if k not in c:
                break
            if d[k] > c[k]:
                break
        else:
            print('Yes')
            exit()
    print('No')

ABC181E - Traveling Salesman among Aerial Cities

Break through in 36 and a half minutes. WA2. There is no choice but to try each pair with the teacher one by one. After trying, the total is calculated every time and it becomes * O * (* N * 2 </ sup>) and TLE. So, if you take the cumulative sum from the front and back, you can make it * O * (* N *). The best transformation form of the teacher is even, I thought that * O * (1) would not be required, but it is troublesome. So I skipped with * O * (log N </ i>) and got a total of * O * ( N </ i> log N </ i>). Implementation calories Was expensive but not difficult.

from itertools import accumulate
from bisect import bisect_left
from collections import Counter

INF = float('inf')

N, M = map(int, input().split())
H = list(map(int, input().split()))
W = list(map(int, input().split()))

W.sort()

c = Counter(H)
h = sorted(k for k in c if c[k] % 2 == 1)
n = len(h)

l = list(accumulate(h[i + 1] - h[i] for i in range(0, n - 1, 2)))
r = list(accumulate(h[i] - h[i - 1] for i in range(n - 1, 0, -2)))

result = INF
for i in range(n):
    t = 0
    a = i // 2 - 1
    if a != -1:
        t += l[a]
    a = (n - 1 - i) // 2 - 1
    if a != -1:
        t += r[a]
    j = bisect_left(W, h[i])
    u = INF
    if j != M:
        u = min(u, W[j] - h[i])
    if j != 0:
        u = min(u, h[i] - W[j - 1])
    t += u
    if i % 2 == 1:
        t += h[i + 1] - h[i - 1]
    result = min(result, t)
print(result)

Recommended Posts