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

Benötigte Zeit

Impressionen

Ich konnte es während des Wettbewerbs nicht lösen, weil andere Besorgungen während des Wettbewerbs eingereicht wurden. Außerdem habe ich viele ABC-Bewertungen, so dass ich morgen morgen keinen neuen Bachacon machen werde. Die FX, die ich jetzt mache, wurden nicht abgeschnitten, deshalb möchte ich die Dinge organisiert halten.

Problem A

Sie müssen sich nur entscheiden, ob Sie direkt oder indirekt sprechen können.

answerA.py

a,b,c,d=map(int,input().split())
print("Yes" if abs(a-c)<=d or (abs(a-b)<=d and abs(b-c)<=d) else "No")

B-Problem

Solche Probleme im Zusammenhang mit Multiplikation und Division haben WA mehrfach ausgegeben, obwohl wahrscheinlich Fehler auftreten. Bei solchen Problemen möchte ich darauf achten, Fälle an den Grenzen zu trennen und Funktionen wie Decke, Boden und Holz zu vermeiden.

answerB.py

x=int(input())
ans=[1]
for i in range(2,x+1):
    k=2
    while True:
        a=i**k
        if a<=x:
            ans.append(a)
            k+=1
        else:
            break
print(max(ans))

C-Problem

Die K-te kleinste wird in der Wörterbuchreihenfolge berechnet, aber die Wörterbuchreihenfolge wird nach ** alphabetischer Reihenfolge ** und ** Länge ** berechnet. Zuerst schrieb ich den Code, der sich auf ** alphabetische Reihenfolge ** und TLE konzentrierte, aber als ich die Einschränkung ** Länge ** hinzufügte, konnte ich AC.

answerC.py

s=input()
l=len(s)
k=int(input())
alp=[chr(i) for i in range(97, 97+26)]
ans=set()
for i in range(26):
    for j in range(l):
        if s[j]==alp[i]:
            for m in range(j,min(l,j+k)):
                ans.add(s[j:m+1])
    if len(ans)>=k:
        break
print(sorted(list(ans))[k-1])

D Problem

Ich konnte es nicht lösen, weil ich während des Bachacons etwas zu tun hatte, aber es war nicht so schwierig. ** Es gab das Gefühl, dass Elemente, die ersetzt werden können (möglicherweise mehrfach ersetzt werden), ersetzt werden können, ohne andere Elemente zu ersetzen **, also habe ich es ohne Beweis bestanden ( ✳︎ 1). ** Ich denke, es ist schwierig, regelmäßig nicht zertifizierte Dinge zu tun **, deshalb bereue ich es. Unter der Annahme, dass dies korrekt ist, erstellen wir einen Union-Find-Baum **, dessen Primzahl eine Menge ist, die austauschbare Elemente enthält, und verwenden dann die Gruppierungsfunktion, um jede Primmenge zu trennen. Wenn die Verarbeitung bis zu diesem Punkt durchgeführt werden kann, sollte der Rest berücksichtigt werden, wenn $ p_i = i $ für die in jeder Primzahl enthaltenen Elemente so viel wie möglich enthält. Da die Primmenge den Indexwert enthält, kann sie hier erhalten werden, indem ** die Produktmenge (gemeinsamer Teil) der Primmenge und die Menge der Elemente von p genommen werden, deren Index dieses Element ist **. .. Für die Produktmenge wird set_intersection mit der gewünschten Menge als Argument ausgeführt, und die Gesamtlänge der Produktmenge wird für jede Primmenge berechnet, um den Maximalwert von i so zu ermitteln, dass $ p_i = i $. (✳︎2)

(✳︎1)… Der mathematische Beweis ist in Antwort geschrieben, daher werde ich ihn überspringen, aber der sinnliche Beweis lautet wie folgt. Ich werde.

(✳︎2)… Für die Verwendung von set_intersection habe ich auf [diesen Blog] verwiesen (https://phst.hateblo.jp/entry/2016/09/19/004249).

answerD.cc

//Referenz: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Einschließen
#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge
#include<iterator>//set_intersection,set_union,set_Wegen des Unterschieds

using namespace std;
typedef long long ll;

//Makro
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach ll
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXR 100000 //10^5:Maximale Reichweite(Wird für die Aufzählung von Primzahlen usw. verwendet.)

//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)
    map<ll,vector<ll>> group;

    //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)];
    }

    void grouping(ll n){ //Gruppierung von Elementarsätzen
        for(ll i=0;i<n;i++){
            if(group.find(parent[i])==group.end()){
                group[parent[i]]=vector<ll>(1,i);
            }else{
                group[parent[i]].push_back(i);
            }
        }
    }
};


signed main(){
    ll n,m;cin >> n >> m;
    UnionFind uf(n);
    vector<ll> p(n);REP(i,n){cin >> p[i];p[i]-=1;}
    REP(i,m){
        ll x,y;cin>>x>>y;
        uf.unite(x-1,y-1);
    }
    REP(i,n)uf.root(i);
    uf.grouping(n);
    ll ans=0;
    for(auto j=uf.group.begin();j!=uf.group.end();j++){
        vector<ll> value=j->S;
        //REP(i,value.size()) cout << value[i] << " ";
        vector<ll> vecinter;
        vector<ll> value2;REP(i,value.size()) value2.PB(p[value[i]]);
        sort(ALL(value));sort(ALL(value2));
        //Vergiss nicht zu sortieren
        set_intersection(ALL(value),ALL(value2),back_inserter(vecinter));
        //cout << ans << endl;
        ans+=vecinter.size();
        //cout << endl;
    }
    cout << ans << endl;
}