[PYTHON] Rückblick auf ABC155

Dies ist mein erster Beitrag. Vielen Dank. Ich werde die Überprüfung von ABC155 zusammenfassen, die gestern in der Praxis durchgeführt wurde.

Ein Problem

Problemstellung

Für die Anzahl der Drillinge wird das Triplett als "arm" bezeichnet, wenn zwei gleich und das andere unterschiedlich sind. Geben Sie bei den drei Ganzzahlen A, B und C Ja ein, wenn Ihnen dieses Triplett leid tut, oder Nein, wenn Sie dies nicht tun.

Antwortbeispiel

a = set(map(int, input().split()))
if len(a) == 2:
  print("Yes")
else:
  print("No")

Sie können beurteilen, ob es Ihnen leid tut oder nicht, indem Sie die Anzahl der Elemente mit set set () überprüfen.

B Problem

Problemstellung

Sie sind ein Einwanderungsbeamter im Königreich AtCoder. Einwanderungsdokumente enthalten mehrere Ganzzahlen, und Sie müssen feststellen, ob sie die Bedingungen erfüllen. Die Allgemeinen Geschäftsbedingungen verlangen, dass die Teilnahme nur dann genehmigt wird, wenn die folgenden Bedingungen erfüllt sind: Alle in das Dokument geschriebenen Ganzzahlen, die gerade sind, sind durch 3 oder 5 teilbar. Wenn Sie die oben genannten Regeln befolgen, drucken Sie GENEHMIGT, wenn Sie Einwanderer mit N ganzen Zahlen A1, A2,…, AN im Dokument genehmigen. Andernfalls drucken Sie VERWEIGERT.

Antwortbeispiel

N = int(input())
A = list(map(int, input().split()))
flag = 0
for i in range(N):
  if A[i] % 2 == 0:
    if A[i] % 3 == 0 or A[i] % 5 == 0:
      pass
    else:
      flag = 1
      break
if flag == 0:
  print("APPROVED")
else:
  print("DENIED")

Wenn es eine gerade Zahl gibt, die nicht durch 3 oder 5 teilbar ist, schreiben Sie das Flag neu und brechen Sie es. Schließlich wird entsprechend dem Wert des Flags ausgegeben.

C Problem

Es gibt N Abstimmungsblätter, und die Zeichenfolge $ S_i $ wird auf das Blatt $ i \ (1 ≤ i ≤ N) $ geschrieben. Geben Sie alle Zeichenfolgen, die am häufigsten geschrieben wurden, in aufsteigender Reihenfolge in lexikalischer Reihenfolge aus.

Zuerst habe ich ein Diktat erstellt und die Zeichen in den Schlüssel und die Anzahl der Vorkommen im Wert eingegeben. .. .. TLE. Ich hatte das Gefühl, dass es nur eine Flagge gab, die heute nicht funktionierte.

Beispielantwort (TLE)

N = int(input())
dic = {}
for i in range(N):
  s = str(input())
  if not s in dic:
    dic[s] = 1
  else:
    dic[s] += 1
max_k_list = [kv[0] for kv in dic.items() if kv[1] == max(dic.values())]
max_k_list = sorted(max_k_list)
for i in max_k_list:
  print(i)

~~ Der Grund für TLE hier ist wahrscheinlich, dass die erste for-Anweisung und die nachfolgende, wenn nicht s in dic: berechnet werden, nahe an $ O (N ^ 2) $ zu liegen. ~~ (Wenn nicht, bitte kommentieren) max_k_list = [kv[0] for kv in dic.items() if kv[1] == max(dic.values())] Es war $ O (N ^ 2) $, indem jedes Mal der Maximalwert in der for-Anweisung ermittelt wurde. Da sich der Maximalwert nicht ändert, können Sie unnötige Berechnungen vermeiden, indem Sie ihn außerhalb der Schleife platzieren, und Sie können ihn zu $ O (N) $ machen. (Ich habe vergessen, dass ich dies zum Zeitpunkt der AC geändert habe ...) ~~ Schließlich war es eine gute Idee, das Sammlungsmodul zu verwenden. ~~

Antwortbeispiel (AC)

import collections

N = int(input())
a = []
for i in range(N):
  a.append(str(input()))
a = collections.Counter(a)
b = max(a.values())
max_k_list = [kv[0] for kv in a.items() if kv[1] == b]
max_k_list = sorted(max_k_list)
for i in max_k_list:
  print(i)

Diesmal war ABCs 3 komplett, also konnte ich es bisher nur lösen. Als Reflexion konnte ich nicht um 9 Uhr anfangen, weil ich das Spiel spielte. Die Antwortgeschwindigkeit war extrem langsam, da vergessen wurde, TLE im C-Problem zu sortieren oder nutzlos zu machen. Besonders heute war D sehr schwierig, deshalb musste ich schnell bis C lösen. Danach ist es notwendig, sich einfach daran zu gewöhnen, es stetig zu lösen. .. (Ich kann es scheinbar nicht tun)

D Problem

Ich habe versucht, es zu implementieren, indem ich mir die Erklärung von Youtube angesehen habe. Ich habe nicht bemerkt, dass es in einer 2-minütigen Suche gelöst werden kann. Ich frage mich, ob es notwendig ist, sich an diesen Bereich zu gewöhnen.

n, K = map(int, input().split())
a = sorted(list(map(int, input().split())))
inf = 10**18 + 1
l = -1 * inf
r = inf
while(l + 1 < r):
  c = (l + r)//2
  count = 0
  for i in range(n):
    #a[i]Fallklassifizierung durch das Zeichen von
    #a[i] <Wenn es ein k gibt, das 0 ist, gibt es ein k<Wenn j, dann a[i]*a[j]Ist kleiner als ein bestimmter Wert x.
    if a[i] < 0:
      start = -1 #OUT
      end = n #OK
      while start + 1 < end:
        mid = (start + end) //2
        if a[i] * a[mid] < c:
          end = mid
        else:
          start = mid
      count += (n-end)
      if start < i:
        count -= 1
    else:#a[i]Da das Vorzeichen von umgekehrt ist, kann die dem vorherigen entgegengesetzte Operation ausgeführt werden.
      start = -1 #OK
      end = n #OUT
      while start + 1 < end:
        mid = (start + end)//2
        if a[i] * a[mid] < c:
          start = mid
        else:
          end = mid
      count += end
      if a[i] * a[i] < c:
        count -= 1
  count = (count // 2)
  if count < K:
    l = c
  else:
    r = c
print(l)

Es war jedoch TLE. Es scheint, dass C ++ es rechtzeitig schaffen kann, Python jedoch nicht. .. .. Leute, die AC sind, scheinen numpys np.searchsorted gut zu verwenden, um es zu lösen.