[PYTHON] Codeforces Runde # 481 (Div. 3) Bacha Review (9/24)

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Diesmal konnte ich es ohne große Fehler bestehen. Es ist ein guter Trend, also werde ich weiterhin mein Bestes geben.

Es gab einen Teil, der stecken blieb, aber ich würde gerne mein Bestes geben, um jedes Mal einen stabilen Zug wie diesen zu machen.

Problem A

Von der rechten Seite der Sequenz aus gesehen ** stellen Sie sicher, dass dieselbe Nummer nicht zweimal erscheint **. Schauen Sie sich daher die Zahlen auf der rechten Seite der Zahlenspalte an und speichern Sie, welche Zahl in $ s $ der Menge erscheint. Wenn es zu diesem Zeitpunkt nicht in $ s $ enthalten ist, fügen Sie es in die Antwort des Arrays ans in der Antwort ein. Wenn es enthalten ist, sehen Sie sich die nächste Nummer an.

A.py

n=int(input())
a=list(map(int,input().split()))[::-1]
s={a[0]}
ans=[str(a[0])]
for i in range(1,n):
    if a[i] not in s:
        s.add(a[i])
        ans.append(str(a[i]))
print(len(ans))
print(" ".join(ans[::-1]))

B-Problem

Die Zeichenfolge kann wie unten gezeigt in einen fortlaufenden Teil und einen nicht aufeinanderfolgenden Teil von $ x $ unterteilt werden.

Wenn die Länge $ l $ des fortlaufenden Teils dieses ** $ x $ auf 2 oder weniger ** eingestellt werden kann, ist das Thema erfüllt. Da die dafür erforderliche Mindestanzahl an Löschungen mit $ min (0, l-2) $ berechnet wird, überprüfen Sie, wie lange $ x $ kontinuierlich ist. Hier können Sie den fortlaufenden Teil von ** $ x $ leicht finden, indem Sie die groupby-Funktion ** wie folgt verwenden.

B.py

from itertools import groupby
n=int(input())
s=[]
for i in groupby(input(),lambda x:x=="x"):
    s.append(list(i[1]))
#s=list(groupby(input(),lambda x:x=="x"))
ans=0
for i in s:
    if i[0]=="x":
        ans+=max(0,len(i)-2)
print(ans)

C-Problem

Es ist ein Problem, ** jede Schlafsaalnummer und Zimmernummer im Schlafsaal aus der Zimmernummer für alle Schlafsäle wiederherzustellen **. Zur Zeit habe ich die Zimmernummern für alle Schlafsäle wie folgt aufgeschrieben, um zu verstehen, wie die Nummern lauten.

Achten Sie auch auf den ** Raum mit der kleinsten Raumnummer ** in jedem Schlafsaal, $ 1 \ rightarrow 1 + a \ _1 \ rightarrow 1 + a \ _1 + a \ _2 \ rightarrow… \ rightarrow 1 + a \ _1 + Da es sich um die kumulative Summe von a \ _2 +… + a \ _ {n-1} $ handelt, speichern Sie diese als Array $ s $. Wenn zu diesem Zeitpunkt die angegebene Zimmernummer $ b \ _i $ ist, entspricht der Schlafsaal, in dem Sie sich befinden, dem Index des größten Elements unter $ b \ _i $ im ** Array $ s $ ** ( $ bisect $ _ $ right $). Außerdem muss die Zimmernummer im Schlafsaal nur ab $ b \ _i $ berücksichtigt werden, was die Differenz zum größten zuvor erhaltenen Faktor darstellt.

Wenn Sie die obigen Schritte für $ i $ ausführen, können Sie dieses Problem mit $ O (m \ log {n}) $ lösen.

C.py

n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
from itertools import accumulate
s=list(accumulate([1]+a))[:-1]
from bisect import bisect_right
#print(s)
ans=[]
for i in range(m):
    c=bisect_right(s,b[i])-1
    #print(c)
    ans.append(str(c+1)+" "+str(b[i]-s[c]+1))
for i in range(m):
    print(ans[i])

D Problem

Es ist ein Problem, das ich sehen konnte, aber ich konnte den Code ziemlich schnell implementieren, so dass ich ein wenig über die jüngsten Erfolge von Bacha nachdachte.

Wenn du gierig denkst, hast du viel Freiheit, also habe ich beschlossen, es irgendwo zu reparieren. Zu diesem Zeitpunkt entschied ich mich, beide Enden zu reparieren. Derzeit gibt es insgesamt 9 Fälle, in denen beide Enden von $ a [0] und a [n-1] $ weder um $ -1,0 noch um + 1 $ geändert werden.

Daher werden wir in Betracht ziehen, eine Funktion $ check $ zu definieren, die die Anzahl der Operationen basierend auf den Änderungen an beiden Enden zurückgibt. Erstens ** $ abs (a [n-1] -a [0]) $ Muss ein Vielfaches von $ n-1 $ ** sein (gibt $ inf $ zurück, wenn es kein Vielfaches von $ n-1 $ ist). Die ** Toleranz zu diesem Zeitpunkt beträgt $ \ frac {a [n-1] -a [0]} {n-1} $ **. Daher sind $ a [1] -a [0], a [2] -a [1],…, a [n-1] -a [n-2] $ alle $ \ frac {a [n-1] ] -a [0]} {n-1} $ Wir werden ** von vorne gierig prüfen. Wenn zu diesem Zeitpunkt entweder $ + 1 oder -1 $ geändert wird und es zu $ \ frac {a [n-1] -a [0]} {n-1} $ wird, wird die Änderung gierig durchgeführt. Zählen Sie die zu ändernden Vorgänge. Wenn es zu diesem Zeitpunkt ein Element gibt, dessen Toleranz nicht $ \ frac {a [n-1] -a [0]} {n-1} $ für eine Änderung von $ + 1,0, -1 $ ist Gibt $ inf $ zurück. Wenn alle oben genannten Urteile geklärt sind, wird die Anzahl der gezählten Operationen zurückgegeben.

Aus dem Obigen kann die Anzahl der Operationen auf jeder der 9 Arten berechnet werden, und der Minimalwert wird ausgegeben. Wenn ** der Mindestwert $ inf $ ** ist, ist die Bedingung nicht erfüllt, sodass -1 ausgegeben wird.

Beachten Sie auch, dass Sie möglicherweise einen Fehler machen, wenn Sie ihn selbst implementieren **, ohne die Anzahl der Operationen an beiden Enden zu zählen **. Außerdem dachte ich, es wäre mühsam, die Fälle zu trennen, also gebe ich im Fall von ** $ n = 1,2 $ zuerst 0 aus **. Außerdem hatte ich das Gefühl, dass ich einen Fehler machen würde, wenn die Toleranz negativ wäre. In diesem Fall habe ich sie ** umgedreht, um die Toleranz nicht negativ zu machen.

D.py

n=int(input())
b=list(map(int,input().split()))
if n==1 or n==2:
    print(0)
    exit()
inf=10**12
#x,y ist der Änderungsbetrag(0,-1,+1),9 Möglichkeiten
def check(x,y):
    global b,n
    ret=0
    if x!=0:
        ret+=1
    if y!=0:
        ret+=1 
    a=[i for i in b]
    a[0]+=x
    a[n-1]+=y
    #In aufsteigender Reihenfolge
    if a[n-1]<a[0]:
        a=a[::-1]
    if (a[n-1]-a[0])%(n-1)!=0:
        return inf
    d=(a[n-1]-a[0])//(n-1)
    for i in range(n-1):
        if a[i+1]-a[i]==d:
            pass
        elif a[i+1]-a[i]==d+1:
            a[i+1]-=1
            ret+=1
        elif a[i+1]-a[i]==d-1:
            a[i+1]+=1
            ret+=1
        else:
            return inf
    return ret

ans=inf
for i in range(-1,2):
    for j in range(-1,2):
        ans=min(ans,check(i,j))
        #print(i,j,check(i,j))
if ans==inf:
    print(-1)
else:
    print(ans)

E Problem

Es gab einen Fall, über den ich vergessen habe nachzudenken, und ich habe 2WA ausgestellt, also bereue ich es. Wenn Sie ruhig denken, sollte es auf mindestens 1WA unterdrückt worden sein.

Um zu überlegen, welcher Wert gültig ist, betrachten Sie zunächst die Bedingung als ** mit nur ** $ x $ aufgelisteten Personen . Zu diesem Zeitpunkt beträgt die Änderung der Anzahl der Personen an der $ i $ -ten Bushaltestelle $ a \ _i $, sodass nach dem Durchfahren jeder Bushaltestelle $ x + a \ _0, x + a \ _0 + a \ _1,…, x + a Nur \ _0 + a \ _1 +… + a \ _ {n-1} $ ist an Bord. Daher können Sie sehen, dass ** alle 0 oder mehr und $ w $ oder weniger ** (✳︎) sein sollten. Daher wird $ a \ _0, a \ _0 + a \ _1,…, a \ _0 + a \ _1 +… + a \ _ {n-1} $ durch die kumulative Summe berechnet, und die Maximal- und Minimalwerte in diesem werden berechnet. Sagen wir $ u bzw. d $. Wenn hier $ x + u \ leqq w $ und $ x + d \ geqq 0 $ erfüllt sind, ist (✳︎) erfüllt, wenn eine Bushaltestelle passiert wird ( Achten Sie nur auf die Maximal- und Minimalwerte! **). Sie müssen auch ** $ 0 \ leqq x \ leqq w $ ** treffen (es war 2WA, weil ich das vergessen habe, sorry). Daher sind $ x + u \ leqq w $ und $ x + d \ geqq 0 $ und $ 0 \ leqq x \ leqq w $ erfüllt. Wenn Sie also alle ** zusammenführen **, $ max (0, -d) Sie können die Anzahl der Ganzzahlen $ x $ ermitteln, die \ leqq x \ leqq min (w, wu) $ erfüllen, und ** den Fall betrachten, in dem es keinen gemeinsamen Teil gibt **, dann $ min (0, min (w, wu)). ) -Max (0, -d) + 1) $.

(Das Obige ist eine zusammenhängende Überlegung und die Implementierung ist einfach, aber während des Wettbewerbs wurde es ** schmutzige Implementierung und Überlegung **. Ich bedauere es.)

E.py

n,w=map(int,input().split())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
u,d=max(b),min(b)
print(max(0,min(w,w-u)-max(0,-d)+1))

E2.py

#Umsetzung während des Wettbewerbs
n,w=map(int,input().split())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
u,d=max(b),min(b)
if u-d>w:
    print(0)
    exit()
if u>w:
    print(0)
    exit()
ran=[max(0,-d),min(w,w-u)]
if ran[1]<ran[0]:
    print(0)
    exit()
print(ran[1]-ran[0]+1)

F Problem

Es war gefährlich, weil ich es am Anfang falsch verstanden habe. Erstens, als Problemstellung, wenn es zwei Personen gibt, $ a, b $, $ r \ _a > r \ _b $ und $ a, b $ nicht streiten, dann wird $ a $ der Mentor von $ b $ sein. können.

Wenn hier nur die erste Bedingung verwendet wird, kann sie leicht erhalten werden, indem der Index mit $ bisect $ _ $ left $ abgerufen wird, indem der Wert von ** $ r $ in aufsteigender Reihenfolge ** (** groß und klein) angegeben wird. Werden in aufsteigender Reihenfolge gezählt! **). Wenn Sie die zweite Bedingung hinzufügen, nachdem Sie die erste Bedingung berücksichtigt haben, können Sie sehen, dass ** diejenigen ausgeschlossen sind, die streiten, während sie eine Bedingung erfüllen **.

Daher ist die Anzahl der Personen, die die $ i $ -te Person ($ r \ _i $) betreuen kann, ** (die Anzahl der Personen mit geringeren Fähigkeiten als ① $ r \ _i $) - (② $ r \ _i $) Die Anzahl der Personen mit geringen Fähigkeiten, die sich jedoch streiten) **. $ Check [i]: = $ (die Anzahl der Personen, deren Fähigkeiten in der $ i $ -ten streitenden Person niedriger sind als $ r \ _i $), $ p: = $ (Fähigkeiten jeder Person) $ Check $ wird gezählt, wenn Sie eine Reihe von Argumenten erhalten, und $ p $ sortiert nur die Eingabe. Daher entspricht ① dem Index (0-indiziert), wenn $ bisect $ _ $ left (p, r \ _ i) $ angewendet wird, und ② entspricht $ check [i] $.

Verschieben Sie von oben aus $ i $ in der Reihenfolge, speichern Sie die Antwort im Array $ ans $ und geben Sie sie schließlich als Antwort aus. Außerdem beträgt der Berechnungsbetrag $ O (k + n \ log {n}) $.

F.py

n,k=map(int,input().split())
r=list(map(int,input().split()))
check=[0]*n
for i in range(k):
    x,y=map(int,input().split())
    x-=1
    y-=1
    if r[x]>r[y]:
        check[x]+=1
    if r[y]>r[x]:
        check[y]+=1
from bisect import bisect_left
ans=[0]*n
p=sorted(r)
for i in range(n):
    b=bisect_left(p,r[i])
    ans[i]=str(b-check[i])
print(" ".join(ans))

G Problem

Ich fragte mich, ob es zu viel Raum für Berechnungen gab und die Problemstellung lang war, aber ich habe den Beat nur durch die Implementierung verpasst. Auch wenn ich es nur implementiert habe, hat es ungefähr 30 Minuten gedauert, um es zu lösen, also möchte ich mich bemühen, es in ungefähr der Hälfte der Zeit zu bestehen.

Erstens werden die folgenden zwei Punkte in der Problemstellung häufig übersehen.

・ Sie können nicht mehrere Prüfungen an einem Tag ablegen, aber aufgrund der Einschränkung des Problems gibt es keine derartigen Eingaben. ・ Die Vorbereitung muss nicht kontinuierlich sein

Zu diesem Zeitpunkt dachte ich, ich könnte mit der gierigen Methode ** arbeiten, die sich auf die Prüfung vorbereitet, die dem Prüfungstermin am nächsten liegt. Diese gierige Methode ist richtig, da es keinen Vorteil hat, zuerst entfernte Prüfungstermine vorzubereiten. Dies kann auch dadurch gezeigt werden, dass selbst wenn zuerst ein entfernter Testtermin vorbereitet wird, dieser durch eine Vorbereitung für einen näheren Testtermin ** ersetzt wird. Daher werden wir diese gierige Methode unten implementieren.

Bereiten Sie zunächst die folgenden vier Datenstrukturen vor. Die Gründe, warum jeder notwendig ist, werden später beschrieben. Außerdem müssen Sie ① und ② initialisieren, aber ich werde dies nicht erklären, da es nach Erhalt der Eingabe leicht verarbeitet werden kann.

① Sequenz $ Prüfungen [i]: = $ (Eine Sequenz, die den Test enthält (Testdatum, erforderliche Anzahl von Vorbereitungstagen), für die die Vorbereitung am $ i $ Tag gestartet werden kann) ② Sequenz $ ind [i]: = $ ($ i $ Tag ist die Reihenfolge des Eingangs des Tests am Testdatum, aber -1, wenn es kein Testdatum gibt) ③ Array $ ans [i]: = $ (Antwort, die am $ i $ Tag ausgegeben werden soll) ④ Setzen Sie $ cand: = $ (Arrangement Holding (Testdatum, erforderliche Anzahl von Vorbereitungstagen) des fertigen Tests)

Bereiten Sie zunächst ④ ** in aufsteigender Reihenfolge des Testdatums vor, um sich aus dem Test in der Nähe des Testdatums vorzubereiten. Auf diese Weise können Sie sich an jedem Tag aus dem kleinsten Element von $ cand $ vorbereiten. Außerdem werden am ** $ i $ Tag ** weitere Prüfungen für neue Vorbereitungen verfügbar sein. Alles was Sie tun müssen, ist ① in $ cand $ einzufügen und den gesamten Inhalt von $ exams [i] $ einzufügen. Als nächstes ist ** wenn dieser Tag der Testtag ist ** noch nicht fertig, also betrachte den nächsten Tag mit $ ans [i] $ als $ m + 1 $. Dies kann dadurch bestimmt werden, ob $ ind [i] $ -1 ist, wenn ② vorbereitet ist, und wenn $ ind [i] $ nicht -1 ist, betrachten Sie die folgende Operation.

Wir werden in Betracht ziehen, uns auf der Grundlage des obigen Urteils vorzubereiten, aber $ cand $ kann leer sein. In diesem Fall sind wir noch nicht bereit. Betrachten Sie den nächsten Tag mit $ ans [i] = 0 $. Dann vorbereiten. Bei der Vorbereitung müssen Sie sich nur die Mindestprüfung $ cand $ ** ansehen (der Umfang der Implementierung hat sich leicht erhöht, weil Sie sie während des Wettbewerbs nicht bemerkt haben). Wenn ** das Testdatum des Tests bereits abgelaufen ist **, ist die Vorbereitung nicht rechtzeitig, sodass -1 ausgegeben und das Programm beendet wird. In anderen Fällen können Sie Maßnahmen für den Test ergreifen und die Empfangsreihenfolge der Testeingabe in $ ans [i] $ durch $ ind $ ersetzen. Wenn Sie sich nach der Vorbereitung des Tests noch vorbereiten müssen, löschen Sie ihn aus ** $ cand $, verringern Sie die erforderliche Anzahl von Vorbereitungstagen um -1 und fügen Sie ihn erneut ein **.

Nachdem Sie an allen Tagen die oben genannten Schritte ausgeführt haben, können Sie $ ans $ ausgeben, müssen jedoch die Möglichkeit berücksichtigen, dass ** $ cand $ ** noch Elemente enthält. In diesem Fall ist ** gleichbedeutend mit einigen Tests, die nicht rechtzeitig fertig sind **, sodass -1 ausgegeben wird. In allen anderen Fällen wird $ ans $ ausgegeben, da die Prüfungsvorbereitung für alle Prüfungen rechtzeitig erfolgt.

(Der folgende Code ist implementiert, um nicht verschwenderisch zu sein, und die obige Überlegung ist auch nicht verschwenderisch, aber während des Wettbewerbs war es ein Code, der viele Fehler wie ** bedingte Verzweigung ** machen konnte. Er funktioniert mit Reflexen Ist auch gut, aber es kann besser sein, es umzusetzen, nachdem die Überlegungen etwas vertieft wurden.)

G.cc

//Debug-Optionen:-fsanitize=undefined,address

//Compileroptimierung
#pragma GCC optimize("Ofast")

//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//Makro
//für Schleife
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden um 1 dekrementiert.
//FORA ist ein Bereich für Aussagen(Wenn es schwer zu bedienen ist, löschen Sie es)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//Konstante
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays
//Abkürzung
#define PB push_back //Einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares

signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    vector<vector<ll>> exams(n);
    //Für den Tag, an dem es fertig ist
    vector<vector<pair<ll,ll>>> preparation(n);
    //Ind für Testdatum
    vector<ll> ind(n,-1);
    REP(i,m){
        ll s,d,c;cin>>s>>d>>c;
        exams[i]={s-1,d-1,c};
        ind[d-1]=i;
        preparation[s-1].PB(MP(d-1,c));
    }
    vector<ll> ans(n,-1);
    set<pair<ll,ll>> cand;
    REP(i,n){
        REP(j,SIZE(preparation[i])){
            cand.insert(preparation[i][j]);
        }
        if(ind[i]!=-1){
            ans[i]=m+1;
            continue;
        }
        if(SIZE(cand)==0){
            ans[i]=0;
            continue;
        }
        auto j=cand.begin();
        while(j!=cand.end()){
            if(j->S==0){
                j=cand.erase(j);
            }else{
                if(j->F<i){
                    cout<<-1<<endl;
                    return 0;
                }
                ans[i]=ind[j->F]+1;
                pair<ll,ll> p=*j;p.S-=1;
                cand.erase(j);
                if(p.S!=0){
                    cand.insert(p);
                }
                break;
            }
        }
        if(ans[i]==-1)ans[i]=0;
    }
    if(SIZE(cand)==0){
        REP(i,n){
            if(i==n-1)cout<<ans[i]<<endl;
            else cout<<ans[i]<<" ";
        }
    }else{
        auto j=cand.begin();
        while(j!=cand.end()){
            if(j->S!=0){
                cout<<-1<<endl;
                return 0;
            }
        }
        REP(i,n){
            if(i==n-1)cout<<ans[i]<<endl;
            else cout<<ans[i]<<" ";
        }
    }

}