[PYTHON] AtCoder Beginner Contest 182 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Dieses Mal habe ich ungefähr 10 Minuten zu spät teilgenommen. Ich dachte, dass es bis zur letzten Minute gehen würde und reichte es ein, aber es war wirklich letzte Minute. Ich war sowohl beim letzten Mal als auch diesmal gut, aber ich konnte nur spät teilnehmen, also werde ich den Wettbewerb nächste Woche demütigen.

F schien in der Lage zu sein, es bald zu lösen, aber nachdem E es gelöst hatte, dachte ich nach, während ich die Knochen des Fisches zum Abendessen entfernte, also konnte ich es nicht tun. Es ist beschämend.

Auch diesmal beträgt die Einrückungsbreite 2 anstelle der üblichen 4. Aus verschiedenen Gründen war der Bau der Umgebung nicht rechtzeitig. Wenn Sie Lust dazu haben, ändern Sie die Breite auf 4.

Problem A

Ausgabe wie gesagt. Mach einfach die Subtraktion.

A.py

a,b=map(int,input().split())
print(2*a+100-b)

B-Problem

** Es gibt nur 2 bis 1000 Kandidaten für die maximale Anzahl **, also suchen Sie einfach alle. Für eine vollständige Suche ist jedoch ein Paar (maximale Anzahl, GCD-Grad) erforderlich.

B.py

n=int(input())
a=list(map(int,input().split()))
ans=[2,sum(i%2==0 for i in a)]
for j in range(1000,2,-1):
  x=[j,sum(i%j==0 for i in a)]
  if x[1]>ans[1]:
    ans=[x[0],x[1]]
print(ans[0])

C-Problem

Da der Rest 3 ist, sollte die Summe der ** Ziffern ein Vielfaches von 3 ** sein. Überlegen Sie zu diesem Zeitpunkt, wie Sie die Ziffern auswählen, die Sie entfernen möchten, indem Sie ** nur den Rest speichern, nachdem Sie jede Ziffer durch 3 geteilt haben. Daher ist hier $ check [i] $: = (der Rest ist die Anzahl der Ziffern von $ i $).

Wenn die Gesamtzahl der Ziffern von Anfang an 0 ist, wird zunächst 0 ausgegeben. In anderen Fällen ** klassifizieren Sie die Fälle einfach sorgfältig wie unten gezeigt **.

(1) Wenn der Rest der Gesamtzahl der Ziffern 1 beträgt.

[1] $ check [1] \ geqq Wenn 1 $, $ check [1] - = 1 $ bewirkt, dass der Rest der gesamten Ziffern 0 ist. Wenn [2] $ check [1] \ <1 $ ist, bewirkt $ check [2] - = 2 $, dass der Rest der Gesamtziffern 0 ist. [3] In jedem Fall wird bei $ sum (check) = 0 $ eine beliebige Ziffer ausgewählt und gelöscht, sodass das Thema nicht zufrieden ist. Zu diesem Zeitpunkt wird -1 ausgegeben. Es kann auch gezeigt werden, dass es sich unter dieser Bedingung um $ check [2] \ <2 $ handelt.

(2) Wenn der Rest der Gesamtzahl der Ziffern 2 beträgt.

[1] $ check [2] \ geqq Wenn 1 $, $ check [2] - = 1 $ bewirkt, dass der Rest der gesamten Ziffern 0 ist. Wenn [2] $ check [2] \ <1 $ ist, bewirkt $ check [1] - = 2 $, dass der Rest der Gesamtzahl der Ziffern 0 ist. [3] In jedem Fall, wenn $ sum (check) = 0 $ ist, wird eine beliebige Ziffer ausgewählt und gelöscht, sodass das Thema nicht zufrieden ist. Zu diesem Zeitpunkt wird -1 ausgegeben. Wir können auch zeigen, dass es unter dieser Bedingung $ check [1] \ <2 $ ist.

C.py

n=input()
l=len(n)
check=[0]*3
for i in range(l):
  check[int(n[i])%3]+=1
if int(n)%3==0:
  print(0)
elif int(n)%3==1:
  if check[1]>=1:
    check[1]-=1
    if sum(check)==0:
      print(-1)
    else:
      print(1)
  else:
    check[2]-=2
    if sum(check)==0:
      print(-1)
    else:
      print(2)
else:
  if check[2]>=1:
    check[2]-=1
    if sum(check)==0:
      print(-1)
    else:
      print(1)
  else:
    check[1]-=2
    if sum(check)==0:
      print(-1)
    else:
      print(2)

D Problem

Ich habe es falsch verstanden ** und missverstanden, dass jeder Zug nur vollständig ausgeführt werden kann **. In diesem Fall müssen Sie sich nichts ausdenken, um über den Maximalwert nachzudenken, nachdem Sie die kumulierte Summe zweimal genommen haben. Bereiten Sie außerdem zwei Arrays vor, die in der folgenden Diskussion verwendet werden sollen. $ b [i]: = $ ($ i $ th vollständige Reisedistanz) und $ c [i]: = $ ($ i $ th vollständige Reisedistanz kumuliert).

Hier ist es gut, ** separat zu betrachten, wenn es sich nicht vollständig bewegt **. Mit anderen Worten, wenn Sie vollständig auf das $ i (0 \ <i \ <n-2) $ th verschoben sind, können Sie das ** $ i + 1 $ th auf das Maximum verschieben, da es auf halber Strecke sein kann * * ist. Mit anderen Worten, wenn in einem Ausdruck ausgedrückt, ist $ (\ sum \ _ {j = 0} ^ {i} b [j]) + c [i] $ die $ i $ -te Lösung. Sie können sich das als jedes $ i $ vorstellen. Daher kann es implementiert werden, indem $ i $ der Reihe nach erhöht wird, während der Wert von $ \ sum \ _ {j = 0} ^ {i} b [j] $ verwaltet wird. Es kann auch einfach implementiert werden, indem die kumulierte Summe von $ b $ genommen wird. Dies ist der zweite Code.

Da das Obige nicht den Fall abdeckt, in dem es sich nicht einmal bewegt, und den Fall, in dem es sich bei allen Bewegungen vollständig bewegt, fügen Sie diese Fälle hinzu, um den Maximalwert zu ermitteln.

D.py

n=int(input())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
c=list(accumulate(b,func=max))
ans=[0,b[0]]
now=b[0]
for i in range(1,n):
  ans.append(now+c[i])
  now+=b[i]
ans.append(now)
print(max(ans))

D_better.py

n=int(input())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
c=list(accumulate(b,func=max))
d=list(accumulate(b))
ans=[0]+[d[i]+c[i] for i in range(n-1)]+[d[n-1]]
print(max(ans))

E Problem

Es ist ein ähnliches Thema wie HHKB Programming Contest 2020-E Lamps. Angenommen, Sie haben einen ** Block oder einen umrandeten Teil ** einer Linie. Wenn sich in diesem Teil nur eine ** Lampe ** befindet, leuchtet dieser Teil auf. Im Gegenteil, in diesem Fall wird es nicht von der Lampe beleuchtet. In Anbetracht der Zeit der Linie ** ist die Anzahl der in beiden Fällen beleuchteten Quadrate die Antwort **. Bei Zeilen und Spalten ist es ausreichend, jede von ihnen zu invertieren. Berücksichtigen Sie daher zunächst nur die Zeit der Zeilen.

Wenn Sie solche ** durchgehenden Teile zusammen verarbeiten möchten, können Sie zunächst die Lauflängenkomprimierung ** (typisch) durchführen. Mit anderen Worten, im Ausgangszustand ist das Quadrat, an dem die Lampe platziert ist, 1, das Quadrat, an dem der Block platziert ist, ist 0 und das Quadrat, an dem nichts platziert ist, ist -1. Zu diesem Zeitpunkt möchte ich das Teil ohne Blöcke betrachten, also ** komprimieren **, je nachdem, ob eine bestimmte Zelle 0 ist. Das heißt, es sieht aus wie in der Abbildung unten.

Nach dem Komprimieren wie in der obigen Abbildung gezeigt ** sollte der durchgezogene Teil auf 1 gesetzt werden (beleuchtetes Quadrat), wenn der komprimierte Teil mindestens eine 1 enthält. Sie können auch groupby verwenden und $ lambda \ x: x == 0 $ für func angeben, um die Komprimierung durchzuführen (Referenz). ).

Persönlich denke ich, dass ich mich an die Idee der Lauflängenkomprimierung gewöhnen muss. Wenn ich Lust dazu habe, werde ich auch einen zusammenfassenden Artikel zum Thema Lauflängenkomprimierung ** veröffentlichen.

E.py

from itertools import groupby
h,w,n,m=map(int,input().split())
check1=[[-1]*w for i in range(h)]
check2=[[-1]*h for i in range(w)]
for i in range(n):
  a,b=map(int,input().split())
  check1[a-1][b-1]=1
  check2[b-1][a-1]=1
for i in range(m):
  c,d=map(int,input().split())
  check1[c-1][d-1]=0
  check2[d-1][c-1]=0
#print(check1)
#print(check2)
for i in range(h):
  x=[(key,list(group)) for key,group in groupby(check1[i],key=lambda x:x==0)]
  now=0
  for k,g in x:
    if not k and 1 in g:
      for j in g:
        check1[i][now]=1
        now+=1
    else:
      now+=len(g)
for i in range(w):
  x=[(key,list(group)) for key,group in groupby(check2[i],key=lambda x:x==0)]
  now=0
  for k,g in x:
    if not k and 1 in g:
      for j in g:
        check2[i][now]=1
        now+=1
    else:
      now+=len(g)
ans=0
for i in range(h):
  for j in range(w):
    if check1[i][j]==1 or check2[j][i]==1:
      ans+=1
#print(check1)
#print(check2)
print(ans)

F Problem

Ich habe keine Lust, es zu lösen. Ich werde diesmal nicht lösen.