[PYTHON] AtCoder Beginner Contest 080 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Ich habe das Gefühl, dass zum ersten Mal seit langer Zeit alles richtig gelöst wurde. Da das D-Problem jedoch durch das Formular getäuscht und der Algorithmus festgelegt wurde, bedauere ich es.

Problem A

Geben Sie einfach den kleineren aus

answerA.py

n,a,b=map(int,input().split())
print(min(a*n,b))

B-Problem

Teilen Sie in der while-Anweisung durch 10, um die Summe jeder Ziffer zu ermitteln.

answerB.py

n=int(input())
k=n
f=0
while k!=0:
    f+=(k%10)
    k//=10
print("Yes" if n%f==0 else "No")

C-Problem

Das Problem eines solchen Musters lässt Sie an DP usw. zweifeln, aber selbst wenn Sie im Voraus entscheiden, ob Sie in jeder Zeitzone öffnen und eine vollständige Suche durchführen möchten, höchstens $ 2 ^ {10} -1 = 1023 $ (immer einmal) (Weil es offen ist), also weiß ich, dass ich pünktlich sein werde. Um zu sehen, was mit Ihren Gewinnen passiert, wenn Sie entscheiden, ob in jeder Zeitzone geöffnet werden soll oder nicht, überprüfen Sie, ob n Geschäfte im Einkaufsviertel in der Zeitzone geöffnet sind, für die Sie sich entschieden haben (bis zu 10). Da es aufgezeichnet wird, ist es O (n), und da es den Gewinn berechnet, der der Anzahl der überprüften Geschäfte entspricht, ist es O (n), sodass Sie sehen können, dass es rechtzeitig für den Berechnungsbetrag ist.

answerC.py

n=int(input())
f=[list(map(int,input().split())) for i in range(n)]
p=[list(map(int,input().split())) for i in range(n)]
ma=-10000000000000
for i in range(1,2**10):
    check=[0]*n
    for j in range(10):
        if (i>>j) & 1:
            for k in range(n):
                check[k]+=f[k][j]
    ma_sub=0
    for i in range(n):
        ma_sub+=p[i][check[i]]
    ma=max(ma,ma_sub)
print(ma)

D Problem

Zuerst bezweifelte ich die Abschnittsplanung, weil ich über die Überlappung der Abschnitte nachdachte, aber es ist nicht für die Abschnittsplanung geeignet, darüber nachzudenken, ** wie viele Abschnitte sich überlappen ** (es ist geeignet, so zu wählen, dass sie sich nicht überlappen). Ich dachte. Infolgedessen war diese Änderung der Richtlinie erfolgreich. Am Ende war es möglich, darüber nachzudenken, wie viele Abschnitte maximal abgedeckt sind, also mit anderen Worten, wie viele Fernsehprogramme gleichzeitig abgespielt werden. Danach ist es effizient, die imos-Methode zu verwenden, wenn der Wert des ** Intervalls ** aktualisiert wird, also habe ich imos verwendet. Darüber hinaus kann bei diesem Problem ** derselbe Kanal kontinuierlich aufgezeichnet werden, auch wenn die End- und Startzeiten eines bestimmten Fernsehprogramms gleich sind **. Daher sollte für jeden Kanal und beim Zählen der endgültigen Nummer die imos-Methode verwendet werden. Ich habe versucht, alles zusammen zu berechnen.

answerD.py

n,c=map(int,input().split())
imos=[[0 for i in range(c)] for j in range(10**5+1)]#1~10**5+1
for i in range(n):
    s,t,_c=map(int,input().split())
    imos[s-1][_c-1]+=1
    imos[t][_c-1]-=1
for i in range(1,10**5+1):
    for j in range(c):
        imos[i][j]+=imos[i-1][j]
imosans=[0]*(10**5+1)
for i in range(10**5+1):
    for j in range(c):
        imosans[i]+=(imos[i][j]>=1)
print(max(imosans))