Die Ergebnisse dieser Zeit

Impressionen

Es war das schwierigste Set in der ABC-Klasse, es war schwierig.

D Ich war zu verwirrt über die Politik des Problems und verbrachte Zeit, aber als ich experimentierte, fand ich heraus, dass das Experiment wichtig ist.

Ich habe das E-Problem eine ganze Weile beobachtet, aber ich habe die gierige Methode nicht ausprobiert. Ich bin unreif, dass ich die Grundlagen der Grundlagen noch nicht gelernt habe, also möchte ich mein Bestes geben ... Ich möchte auf ein Niveau wachsen, auf dem ich mich als wettbewerbsfähiger Profi bezeichnen kann.

Problem A

Sie können zählen, wie viele Vielfache von D vom kleinsten Vielfachen von D über L bis zum größten Vielfachen von D unter R sind. Dies kann als "Decke (l / d) * d, Decke (l / d) * d + d, ..., Etage (r / d) * d" umformuliert werden, daher lautet die Zahl "Etage (r / /"). d) -ceil (l / d) + 1 ".

`A.py`


from math import *
l,r,d=map(int,input().split())
print(floor(r/d)-ceil(l/d)+1)

B-Problem

Sie müssen lediglich sicherstellen, dass die Anzahl der als ungerade geschriebenen Quadrate für alle Zahlen ungerade ist.

`B.py`


n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
    ans+=(i%2==0 and a[i]%2==1)
print(ans)

C-Problem

Ich vermutete für einen Moment eine Faktorisierung, aber es ist schwierig. $ 1 \ leqq x \ leqq \ sqrt {n}, 1 \ leqq y \ leqq \ sqrt {n}, 1 \ leqq z \ leqq \ sqrt {n} $ wurde jedoch sofort durch Betrachten des quadratischen Terms verstanden. , Sie können alle Werte von $ x, y, z $ durchsuchen ($ O (N \ sqrt {N}) $ ist ausreichend).

Außerdem möchten Sie den Wert von $ f (1), f (2),…, f (n) $ finden, der während der vollständigen Suche $ x ^ 2 + y ^ 2 + z ^ 2 + xy + yz beträgt. Sie können den Wert von + zx $ nacheinander von $ 1 $ bis $ N $ aufzeichnen.

`C.py`


from math import *
n=int(input())
l=floor(sqrt(n))+1
ans=[0]*n
def f(a,b,c):
    return a*a+b*b+c*c+a*b+b*c+c*a
for x in range(1,l+1):
    for y in range(1,l+1):
        for z in range(1,l+1):
            g=f(x,y,z)
            if g<=n:
                ans[g-1]+=1
for i in range(n):
    print(ans[i])

D Problem

Die Lösung hat lange gedauert, da ich über das E-Problem nachgedacht habe. Es ist schwierig, das zu lösende Problem auszuwählen ... Wenn es sich um ein Problem der ABC-Klasse handelt, würde ich gerne hart genug arbeiten.

Im Folgenden ist die durch Eingabe angegebene Zahl $ x $ und die Anzahl der Einwohner $ c $.

Selbst wenn Sie popcount ** ehrlich implementieren, wird es natürlich nicht rechtzeitig ** sein, da $ x $ eine sehr große Zahl sein wird. Für eine bestimmte Anzahl von $ K $ beträgt der Wert des Popcount jedoch ungefähr $ \ log {K} $. Aufgrund der Einschränkung des Betreffs dauert es nur ungefähr 5 Mal, um ** Popcount auf 0 ** zu wiederholen ( Unter den Bedingungen des Problems kann gesagt werden, dass es sich um ein nahezu konstantes Vielfaches handelt.)

Lassen Sie uns nun darüber nachdenken, $ f (X_i) $ ehrlich für $ 1 \ leqq i \ leqq N $ zu finden, aber in der ersten Operation kostet es $ O (N) $, alle Ziffern zu überprüfen. Der Gesamtbetrag der Berechnung kostet also $ O (N ^ 2) $. (** Denk ehrlich und reduziere diesen Abfall! **)

** $ f (X_i) $ ändert jedoch nur die $ i $ -Ziffer **. Berücksichtigen Sie daher den Unterschied aufgrund der Inversion dieser Ziffer nach dem Speichern von $ x $. Wenn die $ i $ -Ziffer $ 0 $ ist, ändert sie sich in $ 1 $, sodass sich diese Anzahl von Popcount in $ c-1 $ ändert, und wenn die $ i $ -Ziffer $ 1 $ ist, ändert sie sich in $ 0 $, sodass sich diese Anzahl von Popcount ändert. Es wird $ c + 1 $, und es gibt nur diese beiden Möglichkeiten.

Daher ist es möglich, diese Richtlinie zu erreichen, indem die folgenden beiden in der Vorberechnung vorbereitet werden (beachten Sie, dass der Fall von $ c-1 $ und der Fall von $ c + 1 $ vollständig getrennt werden müssen. Wird benötigt.).

$ i $ Ein Array, das den Rest der Differenz beim Ändern der Ziffern $ m $ speichert →m[i][0]:=2^i \ mod \ (c-1) , m[i][1]:=2^i \ mod \ (c+1) Variable $ l $, die den Rest von $ x $ geteilt durch $ c-1 $ bzw. $ c + 1 $ speichert →l[0]:= x \ mod (c-1) , l[1]:= x \ mod (c+1))

Diese können durch Vorberechnung von $ O (N) $ erstellt werden. Jede Berechnung von $ f (X_i) $ ist $ O (1) $ für die erste Berechnung der Popcount-Differenz, und nachfolgende Popcounts gelten für die normale Popcount. Da dies mit einem konstanten Vielfachen von $ O (\ log {N}) $ unter Verwendung einer Funktion usw. möglich ist, ist es möglich, insgesamt mit $ O (N \ log {N}) $ zu rechnen, und sogar Python kann es sich leisten. Sie können es mit übergeben.

Wenn c zu 1 wird, tritt ** 0 Teilung ** auf, daher ist es notwendig, dies zu vermeiden.

`D.py`


#Teilen Sie durch 0
import math
def popcount(x):
    s=0
    y=int(math.log2(x))+2
    for i in range(y):
        if(x>>i)&1:
            s+=1
    return x%s
n=int(input())
x=input()[::-1]
#Was ich herauskommen werde
c=x.count("1")
#c+1 und c-Denken Sie nur an 1
#c=Zeitteilung von 1
#m[i][j]:2^Mod beim Nachdenken bis zu i(c+j-1)
if c!=1:
    m=[[1%(c-1),1%(c+1)]]
    for i in range(n-1):
        m.append([(2*m[-1][0])%(c-1),(2*m[-1][1])%(c+1)])
    l=[0,0]
    for i in range(n):
        if x[i]=="1":
            l[0]+=m[i][0]
            l[1]+=m[i][1]
            l[0]%=(c-1)
            l[1]%=(c+1)
else:
    m=[[1%(c+1),1%(c+1)]]
    for i in range(n-1):
        m.append([(2*m[-1][0])%(c+1),(2*m[-1][1])%(c+1)])
    l=[0,0]
    for i in range(n):
        if x[i]=="1":
            l[0]+=m[i][0]
            l[1]+=m[i][1]
            l[0]%=(c+1)
            l[1]%=(c+1)
#Ich möchte nur einen ändern, also möchte ich das Ganze

#Verwenden Sie Popcount außer zum ersten Mal
ans=[0]*n
for i in range(n):
    if x[i]=="1":
        if c-1==0:
            ans[i]=0
            continue
        p=(l[0]+(c-1)-m[i][0])%(c-1)
        ans[i]+=1
        while p!=0:
            p=popcount(p)
            ans[i]+=1
    else:
        p=(l[1]+m[i][1])%(c+1)
        ans[i]+=1
        while p!=0:
            p=popcount(p)
            ans[i]+=1
ans=ans[::-1]
for i in range(n):
    print(ans[i])

E Problem

Es ist nicht möglich, eine Kurzschlussidee wie die Auswahl von → $ 2 ^ N $ → DP zu verwenden. Betrachten Sie daher zuerst die Lösung mit der gierigen Methode **.

Hier können Sie für das $ i $ -te Kamel ** $ min (L_i, R_i) $ erhalten, unabhängig von der Reihenfolge, in der $ L_i oder R_i $ erhalten werden. Das ist also die Antwort, nach der ich fragen möchte. Es wird zuerst zur Gesamtsumme "ans" hinzugefügt. Dann ist es einfacher, sich nur eines der Muster ($ L_i-R_i, 0 ) und ( 0, R_i-L_i $) vorzustellen.

Während des Wettbewerbs konnte ich bisher nur auf die Idee kommen, aber ** Denken Sie an das Kamel, das die linke Seite wählen möchte, und an das Kamel, das die rechte Seite wählen möchte ** (($ L_i-R_i, 0 ), ( 0) Es kann mit dem Muster von R_i-L_i $)) und der Richtlinie danach verbunden werden. (** Ich denke, es ist eine natürliche Lösung, eins nach dem anderen zu denken, wenn beide kombiniert werden. Es tut mir leid, dass ich es nicht lösen konnte.)

Darunter kann gesagt werden, dass das Kamel, das die linke Seite wählen möchte, und das Kamel, das die rechte Seite wählen möchte ** wie man die Position des Kamels wählt, nicht stören (unabhängig) **. Dies liegt daran, dass, wenn der erstere ein roter Kreis und der letztere ein blauer Kreis ist, die Position des Kamels wie in der folgenden Abbildung gezeigt verschoben werden kann.

Daher werden wir im Folgenden zunächst überlegen, ob wir gierig die Position des Kamels bestimmen, das die linke Seite wählen möchte. Zu diesem Zeitpunkt werden wir gierig aus denjenigen mit dem größten $ L_i-R_i $ (innerhalb des $ K_i $ th) auswählen, also überlegen Sie sich die optimale Position. ** Die optimale Position kann als die Position umformuliert werden, die die Auswahl nachfolgender Elemente nicht beeinträchtigt **. Zu diesem Zeitpunkt können Sie sehen, dass das $ K_i $ th, das danach die am besten auswählbaren Positionen für andere Kamele aufweist, optimal ist. Da es keine Position gibt, an der Sie mehr erreichen können, wenn Sie sie auf der linken Seite von ** $ K_i $ th platzieren, können Sie anhand dieser Idee erkennen, dass sie korrekt ist. Wenn das $ K_i $ th bereits ausgewählt ist, können Sie außerdem die Position ganz rechts auf der linken Seite auswählen.

Speichern Sie von oben die nicht ausgewählten Positionen in aufsteigender Reihenfolge (verwenden Sie set), wählen Sie die größte Position unter $ K_i $ (neben einem der von Upper_bound ausgewählten Elemente) als Position aus und löschen Sie sie dann aus dem Set. TU es einfach. Wenn zu diesem Zeitpunkt keine entsprechende Position vorhanden ist, kann dieses Element nicht ausgewählt werden. Betrachten Sie daher das nächste Element. Betrachten Sie dies dann nicht nur auf der linken Seite, sondern auch auf der rechten Seite, und die Summe aller ausgewählten Elemente ist die Antwort.

Neue Erkenntnisse zur Gier

→ ** Sie dürfen es in eine Richtung bewegen, die keinen Schaden verursacht **! !! Um es anders herum auszudrücken: ** Gibt es ein Muster, das in anderen Fällen als dem Verschieben erhalten werden kann **?

F Problem

Ich werde diesmal überspringen.

[PYTHON] Acing Programmierwettbewerb 2020