[PYTHON] AtCoder Regular Contest 106 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich hatte nicht genug Zeit, um D zu lösen ... (ich habe ungefähr 10 Minuten später bestanden). ** Ich habe zu viel Zeit verbracht, ohne den Teil zu bemerken, den ich aufgrund des C-Problems verpasst habe ...

Ich denke, es ist das erste Mal, dass ich während des Wettbewerbs an einem blauen Diff (fast gelbem Diff) gearbeitet habe, also nehme ich das als gutes Zeichen und arbeite härter. (Domino-Qualität ...)

Problem A

Da in TL Platz ist, werde ich alle entsprechend suchen. Weder A noch B sind eine sehr große Zahl.

Es könnte etwas interessanter sein, wenn die Abfrage wiederholte Entscheidungen erfordert.

A.py

n=int(input())
x3,x5=[3],[5]
while True:
    if x3[-1]*3<n:
        x3.append(x3[-1]*3)
    else:
        break
while True:
    if x5[-1]*5<n:
        x5.append(x5[-1]*5)
    else:
        break
x3,x5=[i for i in x3 if i<n],[i for i in x5 if i<n]
y3,y5=set(x3),set(x5)
#print(y3,y5)
for i in y3:
    if n-i in y5:
        a,b=i,n-i
        ans1,ans2=0,0
        while a!=1:
            a//=3
            ans1+=1
        while b!=1:
            b//=5
            ans2+=1
        print(ans1,ans2)
        exit()
print(-1)

B-Problem

Da es nicht erforderlich ist, die Anzahl der Operationen zu minimieren, dachte ich, dass die Summe von $ a \ _i, b \ _i $ eines beliebigen Scheitelpunkts gleich sein sollte **, aber ** der Graph ist nicht verkettet. Mir ist aufgefallen wann.

In jedem Fall kann der Wert von $ a $ zwischen verbundenen Scheitelpunkten gut angepasst werden, sodass ** die Summe von $ a \ _i, b \ _i $ der in jeder verbundenen Komponente enthaltenen Scheitelpunkte gleich ist **. Ist eine Bedingung. Die Implementierung mit UnionFind ist nicht schwierig.

B.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

//Unten repräsentieren die Primzahl und der Baum dasselbe.
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; //Nach Set verwalten(key:Repräsentant der Menge, Wert:Ein Array von Elementen der Menge)
    ll n; //Elementanzahl

    //Konstrukteur
    UnionFind(ll n_):n(n_),parent(n_),siz(n_,1){ 
        //Initialisieren, da die Wurzel aller Elemente selbst ist
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    //Holen Sie sich die Wurzel des Baums, zu dem Daten x gehören(Führen Sie auch eine Routenkomprimierung durch)
    ll root(ll x){
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);//Da der Wert des Zuweisungsausdrucks der Wert der zugewiesenen Variablen ist, kann die Route komprimiert werden.
    }

    //X- und y-Bäume zusammenführen
    void unite(ll x,ll y){
        ll rx=root(x);//x root
        ll ry=root(y);//Wurzel von y
        if(rx==ry) return;//Wenn im selben Baum
        //Kleine Menge zu großer Menge zusammenführen(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
    }

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

    //Ermitteln Sie die Größe der Primzahl von x
    ll size(ll x){
        return siz[root(x)];
    }

    //Gruppieren Sie jeden Primsatz
    void grouping(){
        //Führen Sie zuerst die Routenkomprimierung durch
        REP(i,n)root(i);
        //Mit Karte verwalten(Standard-Build verwenden)
        REP(i,n)group[parent[i]].PB(i);
    }

    //Löschen Sie das Prim-Set-System und initialisieren Sie es
    void clear(){
        REP(i,n){parent[i]=i;}
        siz=vector<ll>(n,1);
        group.clear();
    }
};

signed main(){
    //Ausgabespezifikation der Anzahl der Bruchstellen
    //cout<<fixed<<setprecision(10);
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    vector<ll> a(n);REP(i,n)cin>>a[i];
    vector<ll> b(n);REP(i,n)cin>>b[i];
    UnionFind uf(n);
    REP(i,m){
        ll c,d;cin>>c>>d;
        uf.unite(c-1,d-1);
    }
    uf.grouping();
    FORA(i,uf.group){
        ll s=0;
        FORA(j,i.S){
            s+=(a[j]-b[j]);
        }
        if(s!=0){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}

C-Problem

Die Konstruktion, die den Fall erfüllt, ist sofort abgeschlossen (ungefähr 15 Minuten), aber ich habe Zeit verschwendet, indem ich den Satz ** des Problemsatzes vollständig verpasst habe, der -1 ausgibt, wenn er nicht gilt **. Ich tat.

** Überprüfen Sie zunächst die Bedingungen, wenn dies nicht der Fall ist **. Hier lösen die beiden Personen im Betreff das Problem der Abschnittsplanung, und das erstere wird korrekt gelöst, sodass die maximale Anzahl von Abschnitten ausgewählt werden kann. Daher gilt immer $ M \ geqq 0 $, und wenn $ M \ <0 $, wird -1 ausgegeben.

Daher werden wir von nun an die Konstruktion betrachten, wenn $ M \ geqq 0 $. Wie jeder weiß, der das Intervallplanungsproblem gelöst hat, wählen Sie bei Auswahl in aufsteigender Reihenfolge von $ L \ _i $ in aufsteigender Reihenfolge von $ R \ _i $ das Muster des längsten Intervalls des kleinsten $ L \ _i $ aus. Sie können nur die Anzahl der Abschnitte auswählen, die deutlich kleiner sind als im Fall. Die folgende Abbildung ist dargestellt.

In der obigen Abbildung wird angenommen, dass das zuvor erwähnte Minimum $ L \ _i $ und der lange Abschnitt $ l $ Abschnitte enthalten. Zu diesem Zeitpunkt kann der erstere $ n-1 $ Abschnitte auswählen, und der letztere kann nur $ n-l $ Abschnitte auswählen. Daher ist zu diesem Zeitpunkt $ m = l-1 $. Es wird auch $ 0 \ leqq l \ leqq n-1 $ sein, aber wenn $ l = 0 $, $ m = 0 $, also $ 1 \ leqq l \ leqq n-1 \ leftrightarrow 0 \ leqq m \ leqq n- Wenn es 2 $ ist, können Sie es bauen. Auch wenn $ m = n-1, n $, wurde es nicht konstruiert, aber da beide einen oder mehrere Abschnitte auswählen können, gilt $ m = n $ nicht und $ m = n- Wenn es 1 $ ist, wählt Takahashi-kun $ n $ Abschnitte aus und Aoki-kun wählt $ 1 $ Abschnitte aus, aber wenn Takahashi-kun $ n $ Abschnitte auswählt, überlappt sich keiner der Abschnitte. So kann Aoki auch $ n $ Abschnitte auswählen.

Beachten Sie auch, dass das oben Gesagte den Fall von $ n = 1, m = 0 $ nicht berücksichtigt. Dies kann durch einfaches Anordnen der nicht überlappenden Abschnitte bei $ m = 0 $ erfolgen, sodass dies vermieden werden kann, indem zuerst $ m = 0 $ geteilt wird.

Ich denke nicht, dass es so schwierig ist, die obige Abbildung so zu implementieren, wie sie ist.

C.py

n,m=map(int,input().split())
if n==1 and m==0:
    print(1,2)
    exit()
if m==n or m==n-1 or m<0:
    print(-1)
    exit()
ans=[[1,10**7]]
for i in range(m+1):
    ans.append([2*(i+1),2*(i+1)+1])
for i in range(n-m-2):
    ans.append([10**7+2*(i+1),10**7+2*(i+1)+1])
#print(ans)
for i in ans:
    print(i[0],i[1])

D Problem

Ich hatte das Gefühl, dass das D-Problem einfacher war, weil es nicht so schwierig war, nur die Formeltransformation durchzuführen. Während des Wettbewerbs schien es unter Druck zu stehen, aber ich konnte es nicht finden und in den verbleibenden 20 Minuten umsetzen.

Zuerst dachte ich darüber nach, auf den Beitrag jedes $ A \ _i $ zu achten, weil es nur ein Polynom im Summenproblem ist. Dann möchten Sie ** $ (A \ _ L + A \ _R) ^ x $ ** erweitern. Wenn Sie es also nach dem Binomialsatz erweitern, sieht es wie folgt aus.

(A\_L+A\_ R)^x=\_xC\_0 A\_L^x+\_xC\_1 A\_L^{x-1} A\_R+…+\_xC\_x A\_R^x

In Anbetracht des Beitrags eines bestimmten $ A \ _i $ ist ** $ A \ _i $ ein Paar von $ (A \ _L, A \ _R) $ mit allen Zahlen außer sich selbst **, so oben Unter Verwendung der Formel lautet jeder durch den Binomialsatz erweiterte Term wie folgt. (✳︎)

\_xC\_0:A\_i^{x}(A\_1^0+…+A\_{i-1}^0+A\_{i+1}^0+…+A\_{n}^0) \_xC\_1:A\_i^{x-1}(A\_1^1+…+A\_{i-1}^1+A\_{i+1}^1+…+A\_{n}^1) ↓ \_xC\_{x-1}:A\_i^{1}(A\_1^{x-1}+…+A\_{i-1}^{x-1}+A\_{i+1}^{x-1}+…+A\_{n}^{x-1}) \_xC\_{x}:A\_i^{0}(A\_1^{x}+…+A\_{i-1}^{x}+A\_{i+1}^{x}+…+A\_{n}^{x})

Auch wenn es so implementiert ist, sind $ x $ Kandidaten $ k $, $ A \ _i $ Kandidaten $ n $ und jeder der beiden oben genannten Kandidaten, selbst wenn $ \ _xC \ _i $ vorberechnet ist Der Termkoeffizient ist $ x + 1 $, und die Berechnung in $ () $ ist $ n $ mal. Es scheint also, dass selbst wenn Sie es ehrlich tun, es nicht rechtzeitig sein wird. Lassen Sie uns daher über eine weitere Zusammenfassung der Formeln nachdenken, unter der Voraussetzung, dass einige Vorberechnungen durchgeführt werden.

Das heißt, betrachten Sie ** Summieren jedes Binomialkoeffizienten $ \ _xC \ _i $ für jedes $ A \ _i $ **. Dann ist es wie in der folgenden Abbildung gezeigt.

Wenn also diese Summe zusammengesetzt wird, $ (A \ _1 ^ {xi} + A \ _2 ^ {xi} +… + A \ _n ^ {xi}) \ mal (A \ _1 ^ {i} + A \ _2 ^ {i} +… + A \ _n ^ {i}) - (A \ _1 ^ {x} + A \ _2 ^ {x} +… + A \ _n ^ {x}) $ (** Symmetrisch Ich denke, es ist natürlich ** aus Sicht des Sex).

Daher ist zusätzlich zur Vorberechnung des Binomialkoeffizienten $ y [i]: = (A \ _1 ^ i + A \ _2 ^ i +… + A \ _n ^ i) $ Vorberechnung von $ i = 0 Wenn Sie dies mit $ ~ $ k $ ($ O (nk) $) tun, finden Sie die Summe bei $ \ _xC \ _i $ mit $ O (1) $. Daher beträgt der Gesamtbetrag der Berechnung $ O (k ^ 2) $, um die Antwort für jedes $ x $ zu finden.

Aus dem Obigen ergibt sich ein Gesamtbetrag der Berechnung von $ O (n + nk + k ^ 2) = O (k (k + n)) $, was ausreichend schnell ist.

(✳︎)… Von nun an betrachten wir die Bedingung von $ 1 \ leqq L, R \ leqq N, L \ neq R $ anstelle von $ 1 \ leqq L \ leqq n-1, L + 1 \ leqq R \ leqq n $. Es ist jedoch nur erforderlich, die endgültige Antwort zu halbieren und nicht ** Symmetrie **.

D.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 998244353 //10^9+7:Gemeinsames Recht
#define MAXR 1000 //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

template<ll mod> class modint{
public:
    ll val=0;
    //Konstrukteur
    modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
    //Konstruktor kopieren
    modint(const modint &r){val=r.val;}
    //Arithmetischer Operator
    modint operator -(){return modint(-val);} //einstellig
    modint operator +(const modint &r){return modint(*this)+=r;}
    modint operator -(const modint &r){return modint(*this)-=r;}
    modint operator *(const modint &r){return modint(*this)*=r;}
    modint operator /(const modint &r){return modint(*this)/=r;}
    //Aufgabenverwalter
    modint &operator +=(const modint &r){
        val+=r.val;
        if(val>=mod)val-=mod;
        return *this;
    }
    modint &operator -=(const modint &r){
        if(val<r.val)val+=mod;
        val-=r.val;
        return *this;
    }
    modint &operator *=(const modint &r){
        val=val*r.val%mod;
        return *this;
    }
    modint &operator /=(const modint &r){
        ll a=r.val,b=mod,u=1,v=0;
        while(b){
            ll t=a/b;
            a-=t*b;swap(a,b);
            u-=t*v;swap(u,v);
        }
        val=val*u%mod;
        if(val<0)val+=mod;
        return *this;
    }
    //Äquivalenzvergleichsoperator
    bool operator ==(const modint& r){return this->val==r.val;}
    bool operator <(const modint& r){return this->val<r.val;}
    bool operator !=(const modint& r){return this->val!=r.val;}
};

using mint = modint<MOD>;

//E / A-Stream
istream &operator >>(istream &is,mint& x){//Fügen Sie x nicht const hinzu
    ll t;is >> t;
    x=t;
    return (is);
}
ostream &operator <<(ostream &os,const mint& x){
    return os<<x.val;
}

//Leistung
mint modpow(const mint &a,ll n){
    if(n==0)return 1;
    mint t=modpow(a,n/2);
    t=t*t;
    if(n&1)t=t*a;
    return t;
}

//Berechnung des Binomialkoeffizienten
mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];
//Eine Tabelle erstellen
void COMinit() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    FOR(i,2,MAXR){
        fac[i]=fac[i-1]*mint(i);
        inv[i]=-inv[MOD%i]*mint(MOD/i);
        finv[i]=finv[i-1]*inv[i];
    }
}
//Berechnungsteil
mint COM(ll n,ll k){
    if(n<k)return 0;
    if(n<0 || k<0)return 0;
    return fac[n]*finv[k]*finv[n-k];
}

signed main(){
    //Ausgabespezifikation der Anzahl der Bruchstellen
    //cout<<fixed<<setprecision(10);
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    COMinit();
    ll n,k;cin>>n>>k;
    vector<ll> a(n);REP(i,n)cin>>a[i];
    //po
    vector<vector<mint>> po(n,vector<mint>(k+1,0));
    REP(i,n){
        po[i][0]=1;
        REP(j,k){
            po[i][j+1]=po[i][j]*a[i];
        }
    }
    vector<mint> y(k+1,0);
    REP(i,k+1){
        REP(j,n){
            y[i]+=po[j][i];
        }
    }
    vector<mint> ans(k,0);
    FOR(x,1,k){
        mint ans_sub=0;
        REP(j,x+1){
            ans_sub+=(COM(x,j)*((y[x-j])*(y[j])-y[x]));
        }
        ans[x-1]+=ans_sub;
    }
    REP(i,k){
        cout<<ans[i]/2<<endl;
    }
}

Nach dem E-Problem