Rückblick auf den AtCoder Beginner Contest 166 bis Frage E (Python)

Dies ist ein Übersichtsartikel für Anfänger von Wettkampfprofis.

Die Lösung, die ich hier schreibe, wurde geschrieben, während ich mir den Kommentar und die Beiträge anderer Leute ansah. Es ist möglicherweise nicht das, was Sie tatsächlich eingereicht haben.

Ursache dieser Niederlage

Oh, ** Hast du es am Sonntag gemacht? ** **.

Ich wusste nicht, dass es den Wettbewerb gibt. Ich habe den Zeitplan nicht gesehen. Deshalb löse ich das Problem, nachdem der Wettbewerb beendet ist.

A - A?C

Atcoder scheint jeden Samstag einen Wettbewerb abzuhalten. Nächstes Mal werde ich fragen, ob ABC oder ARC stattfinden wird.

Wenn die Eingabe 'ABC' ist, geben Sie 'ARC' aus. Wenn nicht, geben Sie 'ABC' aus.

S = input()
if S == 'ABC':
  print('ARC')
else:
  print('ABC')

B - Trick or Treat

Jede der K Arten von Süßigkeiten wird an Kinder mit der Nummer $ \ boldsymbol {A_k} $ verteilt. Die Frage ist, wie viele Kinder die Süßigkeiten nicht erhalten haben.

Ich denke, Sie sollten die Elemente jeder Anordnung kombinieren, die Duplizierung entfernen, die "Anzahl der Personen, denen Süßigkeiten gegeben wurden" überprüfen und von der Gesamtzahl der Personen abziehen.

N, K = map(int, input().split())
A = []
for _ in range(K):
  d = input()
  A += list(map(int, input().split()))
print(N - len(set(A)))

↓ ist ein Muster, das ich jedes Mal versucht habe, in den eingestellten Typ zu schieben. Dieser war schneller.

N, K = map(int, input().split())
A = set()
for _ in range(K):
  d = input()
  A = A.union(set(map(int, input().split())))
print(N - len(A))

C - Peaks

Die Frage ist, wie viele Observatorien die Bedingung "höher als alle an Sie angrenzenden Observatorien" erfüllen.

Es sieht aus wie ein Grafikproblem ... aber Sie müssen nicht so lange darüber nachdenken. Falsch, wenn das angrenzende Observatorium größer ist als Sie. Stimmt, wenn Sie keine haben. Schließlich habe ich die Anzahl von True überprüft und ausgegeben.

Beachten Sie, dass beide Observatorien mit "gleicher Höhe" falsch sind.

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

good = [True] * N

for _ in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  if H[A] >= H[B]:
    good[B] = False
  if H[A] <= H[B]:
    good[A] = False
print(sum(good))

D - I hate Factorization

A^5 - B^5 = X

Es ist ein Problem, einen Satz von ganzen Zahlen (A, B) auszugeben, der erfüllt.

Wie viel sollten die Bereiche $ A und B $ betragen, um das Limit von $ X \ leq 10 ^ 9 $ zu erreichen? Was ist die Zahl, die $ 10 ^ 9 $ um die fünfte Potenz überschreitet?

n = 1
while n**5 < 10**9:
  n += 1
print(n)
# 64

Ich werde versuchen, das gesamte Gebiet zu durchsuchen, indem ich ungefähr das Doppelte dieses Bereichs nehme.

import itertools

X = int(input())

for a, b in itertools.product(range(128), range(-128, 128)):
  if(a ** 5 - b ** 5 == X):
    print(a, b)
    break

Ich ging durch.

Als ich den Kommentar sah,

n^5 - (n-1)^5 \geq 10^9

Es scheint richtig zu sein, nach $ n $ zu suchen, das zufriedenstellend ist, dh bis zu $ n = 120 $. Das Ergebnis ist in Ordnung, aber lassen Sie uns richtig darüber nachdenken. Solange diese Berechnung erfolgreich ist, ist es auch eine gute Idee, einen möglichst großen Bereich zu durchsuchen.

E - This Message Will Self-Destruct in 5s

"Diese Meldung verschwindet automatisch nach 5 Sekunden."

Die Frage ist, die Zahl zu beantworten, die $ A_i + A_j = j-i $ erfüllt.

Alles wird in itertools.combinations_with_replacement () behandelt. Es wurde TLE.

import itertools

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

count = sum([j-i == A[i-1]+A[j-1] for i, j in itertools.combinations_with_replacement(range(1, N+1), 2)])

print(count)

Ich weiß es nicht und gebe auf. Siehe den Kommentar. Ist es möglich, aus $ O (n ^ 2) $ zu entkommen?

A_i + A_j = j-i

↓

A_i + i = j-A_j

Es ist fertig. Sie müssen nur für jeden Wert einen unabhängigen Status berechnen.

Berechnen Sie für den Wert $ A_i $ den Wert $ L_i = i + A_i $, $ R_i = i --A_i $. Sie können die Anzahl der Kombinationen mit $ L_i = R_j $ berechnen, indem Sie zählen, wie viele Werte in $ R $ bzw. $ L $ enthalten sind.

Deshalb habe ich es mit dem folgenden Code implementiert.

import collections

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

L = [i + A[i] for i in range(N)]
R = [i - A[i] for i in range(N)]

countL = collections.Counter(L)
countR = collections.Counter(R)

print(sum([countL[n] * countR[n] for n in countL.keys()]))

Das ist alles für diesen Artikel.