AtCoder Beginner Contest 181 Rapport de participation

AtCoder Débutant Contest 181 Rapport de participation

ABC181A - Heavy Rotation

Percer en 1 minute. Il suffit d'écrire.

N = int(input())

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

ABC181B - Trapezoid Sum

Il a éclaté en 4 minutes. Il a fallu beaucoup de temps pour changer la formule pour soustraire le total de A à A-1 parce que la formule pour calculer le total de A à B ne sortait pas.

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)

Quand je me suis calmé, la cérémonie s'est déroulée correctement (rires).

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

Percer en 19 minutes. Commencez par google avec la formule de la ligne droite passant par les deux points. N ≤ 10 2 </ sup> Donc * O * (* N * 3 </ sup>) est OK Il m'a fallu un certain temps pour le remarquer. Dans l'exemple d'entrée / sortie, la division de 0 est apparue et je me suis souvenu de la ligne droite de type x = a (rires). Bien que la formule soit légèrement fausse, j'ai eu la chance d'être repris dans l'exemple d'entrée / sortie. Peut être fixé, 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: Si vous multipliez les deux côtés par le terme de division, vous pouvez calculer avec précision avec un entier, et il n'y avait pas de division de 0 ...

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

Percer en 13 minutes et demie. Si vous remarquez que les chiffres supérieurs à 1 000 sont automatiquement des multiples de 8, c'est un problème qui s'arrête là. J'ai donc pu AC avec le code ci-dessous, mais il semble y avoir un bogue. 3 chiffres À l'époque ci-dessus, je n'ai pas utilisé «008» ou «016» comme arbre, et j'ai pensé que cela pourrait être une vérification d'un modèle dans lequel les caractères restants à 4 chiffres sont 0. Cependant, en raison de la limitation du problème, 0 existait-il en premier lieu? ,sûr.

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

Percer en 36 minutes et demie. WA2. Il n'y a pas d'autre choix que d'essayer chaque paire avec l'enseignant un par un. Après avoir essayé, le total est calculé à chaque fois et il devient * O * (* N * 2 </ sup>) et TLE. Donc, si vous prenez la somme cumulée de l'avant et de l'arrière, vous pouvez faire * O * (* N *). La meilleure forme de transformation de l'enseignant est paire, je pensais que * O * (1) ne serait pas nécessaire, mais c'est ennuyeux. J'ai donc sauté avec * O * (log N </ i>) et j'ai obtenu un total de * O * ( N </ i> log N </ i>). C'était cher mais pas difficile.

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