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

Benötigte Zeit

Impressionen

D war Gewerkschaftsfund, ich habe versucht, es ohne viel Verständnis zu benutzen, also habe ich versucht, es zu verstehen. Ich möchte genug Wissen erwerben, um mich mit ABC vertraut zu machen.

Problem A

Überlegen Sie, wie oft Sie auf B yen hören können, ohne c zu überschreiten.

answerA.py

a,b,c=map(int,input().split())
print(min(c,b//a))

B-Problem

Alle Suchen werden in absteigender Reihenfolge vom kleinsten von a und b durchgeführt.

answerB.py

a,b,k=map(int,input().split())
check=0
m=min(a,b)
for i in range(m,0,-1):
    if a%i==0 and b%i==0:
        check+=1
        if check==k:
            print(i)
            break

C-Problem

Wenn Sie der Meinung sind, dass es sich um ein Problem des Musters handelt, das die Konsistenz der Anzahl von Blau und Rot unter Verwendung des Stapels berücksichtigt, fallen alle schließlich ab, sodass am Ende nur die Würfel derselben Farbe übrig bleiben.

answerC.py

s=input()
c=0
for i in s:
    c+=(i=="0")
    c-=(i=="1")
print(len(s)-abs(c))

D Problem

Es war wirklich schwierig ... Oder besser gesagt, die Leistung des Algorithmus reicht nicht aus. UnionFindTree Ich denke, es ist zu unerfahren, um es zu verstehen. Vorerst habe ich UnionFindTree nach Bachacon durch Versuch und Irrtum implementiert (ich habe auf die folgenden zwei Artikel verwiesen [1], [2]), [3]. Erstens ist UnionFindTree eine Datenstruktur, die bestimmt, ob zwei Elemente zu derselben Menge gehören, und verschiedene Mengen mit hoher Geschwindigkeit zusammenführt (ich werde nicht erklären, wie es funktioniert, also kommentieren Sie dies im Code und aus Siehe Referenzartikel.). Wichtig hierbei ist auch, dass ** UnionFindTree nicht geteilt werden kann **. Dieses Problem erfordert eine Teilung (weil die Brücke zusammenbricht) und erfordert etwas Einfallsreichtum (wie in der Antwort erwähnt, aber im Allgemeinen ist es schwierig, den Graphen zu löschen.) ). Hier ist im Endzustand keine der Brücken verbunden **, und wenn Sie den umgekehrten Vorgang ausführen, werden die Brücken einzeln ** hinzugefügt, sodass Sie beim Hinzufügen von Brücken hin und her gehen können. Sie finden die Antwort, indem Sie die Änderungen in der Anzahl der Inseln aufzeichnen. Wenn Sie eine Brücke hinzufügen, die die Eckpunkte a und b verbindet, beträgt die Anzahl der Elemente der Primmenge, die diese Eckpunkte enthält, $ N_a, N_b $ und $ (N_a + N_b) \ times (N_a + N_b-) 1) \ div 2 -N_a \ times (N_a-1) \ div 2-N_b \ times (N_b-1) \ div 2 $ erhöht die Anzahl der Inselpaare, die besucht werden können. Wenn Sie es also mit dem Hinweis implementieren, dass Sie ** die Anzahl der nicht erreichbaren Inselpaare ** (im Vergleich zum Ausgangszustand) möchten:

answerD.cc

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
using namespace std;
typedef long long ll;

//Referenz: https://pyteyon.hatenablog.com/entry/2019/03/11/200000
//Referenz: https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396

class UnionFind {
public:
    vector<ll> parent; //parent[i]Ist der Elternteil von i
    vector<ll> siz; //Ein Array, das die Größe der Primmenge darstellt(Initialisieren Sie mit 1)

    //Vom Konstruktor:Dahinter werden Mitgliedsvariablen initialisiert
    UnionFind(ll n):parent(n),siz(n,1){ //Initialisieren Sie, da zunächst alles root ist
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    ll root(ll x){ //Holen Sie sich die Wurzel des Baums, zu dem die Daten x rekursiv gehören
        if(parent[x]==x) return x;
        //Der Wert des Zuweisungsausdrucks ist der Wert der zugewiesenen Variablen!
        //Pfadkomprimierung(Optimieren Sie Berechnungen, indem Sie Elemente direkt mit der Wurzel verbinden)
        return parent[x]=root(parent[x]);
        //Aktualisieren Sie das übergeordnete Element, wenn Sie rekursiv arbeiten
    }

    void unite(ll x,ll y){ //X- und y-Bäume zusammenführen
        ll rx=root(x);//Die Wurzel von x ist rx
        ll ry=root(y);//y root ry
        if(rx==ry) return; //Wenn im selben Baum
        //Füge einen kleinen Satz zu einem großen Satz zusammen(Zusammengeführt von ry zu rx)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx; //Wenn sich x und y nicht im selben Baum befinden, hängen Sie y root ry an x root rx an
    }

    bool same(ll x,ll y){//Gibt zurück, ob der Baum, zu dem x und y gehören, identisch ist
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    ll size(ll x){ //Grundsatzgröße
        return siz[root(x)];
    }
};

signed main(){
    ll n,m;cin >> n >> m;
    vector< pair<ll,ll> > ab(m);
    for(ll i=m-1;i>=0;i--){cin >> ab[i].first >> ab[i].second;}
    UnionFind uf(n);
    vector<ll> ans(m);ans[0]=(n*(n-1))/2;//cout << ans[0] << endl;
    for(ll i=0;i<m-1;i++){
        //Gleichzeitig finden hier Updates statt
        ll a,b;a=ab[i].first-1;b=ab[i].second-1;
        if(uf.same(a,b)){
        ans[i+1]=ans[i];
        }else{
        ll sa,sb;sa=uf.size(a);sb=uf.size(b);
        ans[i+1]=ans[i]+(sa*(sa-1))/2+(sb*(sb-1))/2;
        uf.unite(a,b);sa=uf.size(a);
        ans[i+1]-=(sa*(sa-1))/2;
        }
    }
    for(ll i=m-1;i>=0;i--){
        cout << ans[i] << endl;
    }
}