[PYTHON] AtCoder Regular Contest 106 Évaluation

Les résultats de cette fois

Impressions de cette époque

Je n'ai pas eu assez de temps pour résoudre D ... (j'ai passé environ 10 minutes plus tard). ** J'ai passé trop de temps sans remarquer la partie que j'ai ratée à cause du problème C ...

Je pense que c'est la première fois que je travaille sur un diff bleu (diff presque jaune) pendant le concours, donc je vais prendre cela comme un bon signe et travailler plus dur. (Qualité Domino ...)

Problème A

Puisqu'il y a de la place dans TL, je vais tout chercher de manière appropriée. Ni A ni B ne sont un très grand nombre.

Cela peut être un peu plus intéressant si la requête nécessite des décisions répétées.

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)

Problème B

Puisqu'il n'est pas nécessaire de minimiser le nombre d'opérations, j'ai pensé que la somme de $ a \ _i, b \ _i $ de n'importe quel sommet devrait être égale **, mais ** le graphe n'est pas concaténé. J'ai remarqué quand.

Dans tous les cas, la valeur de $ a $ peut être bien ajustée entre les sommets connectés, donc ** la somme de $ a \ _i, b \ _i $ des sommets contenus dans chaque composant connecté est égale **. Est une condition. Ce n'est pas difficile à mettre en œuvre avec UnionFind.

B.cc

//Options de débogage:-fsanitize=undefined,address

//Optimisation du compilateur
#pragma GCC optimize("Ofast")

//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#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 est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire

//Ci-dessous, l'ensemble premier et l'arbre représentent la même chose.
class UnionFind{
public:
    vector<ll> parent; //parent[i]Est le parent de i
    vector<ll> siz; //Un tableau représentant la taille de l'ensemble premier(Initialiser avec 1)
    map<ll,vector<ll>> group; //Gérer par set(key:Représentant de l'ensemble, valeur:Un tableau d'éléments de l'ensemble)
    ll n; //Nombre d'éléments

    //constructeur
    UnionFind(ll n_):n(n_),parent(n_),siz(n_,1){ 
        //Initialiser car la racine de tous les éléments est elle-même
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    //Récupère la racine de l'arborescence à laquelle appartient la donnée x(Effectuer également la compression d'itinéraire)
    ll root(ll x){
        if(parent[x]==x) return x;
        return parent[x]=root(parent[x]);//Puisque la valeur de l'expression d'affectation est la valeur de la variable affectée, l'itinéraire peut être compressé.
    }

    //Fusionner les arbres x et y
    void unite(ll x,ll y){
        ll rx=root(x);//x racine
        ll ry=root(y);//racine de y
        if(rx==ry) return;//Quand dans le même arbre
        //Fusionner un petit ensemble dans un grand ensemble(Fusionné de ry à rx)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx;//Lorsque x et y ne sont pas dans le même arbre, attachez la racine y ry à la racine x rx
    }

    //Déterminez si l'arbre auquel appartiennent x et y est le même
    bool same(ll x,ll y){
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    //Obtenez la taille de l'ensemble premier de x
    ll size(ll x){
        return siz[root(x)];
    }

    //Regroupez chaque ensemble principal
    void grouping(){
        //Effectuez d'abord la compression d'itinéraire
        REP(i,n)root(i);
        //Gérer avec la carte(Utiliser la version par défaut)
        REP(i,n)group[parent[i]].PB(i);
    }

    //Supprimer le système prime set et initialiser
    void clear(){
        REP(i,n){parent[i]=i;}
        siz=vector<ll>(n,1);
        group.clear();
    }
};

signed main(){
    //Spécification de sortie du nombre de chiffres fractionnaires
    //cout<<fixed<<setprecision(10);
    //Code pour accélérer la saisie
    //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;
}

Problème C

La construction qui a satisfait le cas a été terminée immédiatement (environ 15 minutes), mais j'ai perdu du temps en manquant complètement la phrase ** de l'énoncé du problème, qui renvoie -1 si elle ne tient pas **. J'ai fait.

Tout d'abord, ** vérifiez les conditions si cela ne tient pas **. Ici, les deux sujets résolvent le problème de planification des sections, et le premier est résolu correctement, de sorte que le nombre maximum de sections peut être sélectionné. Par conséquent, $ M \ geqq 0 $ est toujours valable, et si $ M \ <0 $, -1 est affiché.

Par conséquent, à partir de maintenant, nous considérerons la construction lorsque $ M \ geqq 0 $. Comme le sait quiconque a résolu le problème d'ordonnancement d'intervalle, lors de la sélection par ordre croissant de $ L \ _i $, sélectionnez par ordre croissant de $ R \ _i $ avec le modèle de l'intervalle le plus long du plus petit $ L \ _i $. Vous ne pouvez choisir que le nombre de sections nettement plus petites que dans le cas. La figure ci-dessous est illustrée.

Dans la figure ci-dessus, on suppose que le minimum $ L \ _i $ mentionné précédemment et la section longue incluent des sections $ l $. À ce stade, le premier peut sélectionner des sections $ n-1 $, et le second ne peut sélectionner que des sections $ n-l $. Par conséquent, à ce moment, $ m = l-1 $. De plus, ce sera $ 0 \ leqq l \ leqq n-1 $, mais quand $ l = 0 $, $ m = 0 $, donc $ 1 \ leqq l \ leqq n-1 \ leftrightarrow 0 \ leqq m \ leqq n- Quand c'est 2 $, vous pouvez le construire. De plus, quand $ m = n-1, n $, il n'a pas été construit, mais comme les deux peuvent sélectionner une ou plusieurs sections, $ m = n $ ne tient pas, et $ m = n- Quand il est de 1 $, Takahashi-kun sélectionne $ n $ sections et Aoki-kun sélectionne $ 1 $ sections, mais lorsque Takahashi-kun sélectionne $ n $ sections, aucune des sections ne se chevauche. Ainsi, Aoki peut également choisir des sections $ n $.

Notez également que ce qui précède ne prend pas en compte le cas de $ n = 1, m = 0 $. Cela peut être fait en arrangeant simplement les sections qui ne se chevauchent pas lorsque $ m = 0 $, donc cela peut être évité en divisant d'abord $ m = 0 $.

Je ne pense pas que ce soit si difficile à mettre en œuvre simplement en mettant en œuvre le chiffre ci-dessus tel quel.

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])

Problème D

J'ai senti que le problème D était plus facile car il n'était pas si difficile de faire simplement la transformation de formule. Pendant le concours, cela semblait être sous pression, mais je n'ai pas pu le trouver et le mettre en œuvre dans les 20 minutes restantes.

Tout d'abord, j'ai pensé à ** faire attention à la contribution de chaque $ A \ _i $ car ce n'est qu'un polynôme dans le problème de somme. Ensuite, vous voulez développer ** $ (A \ _ L + A \ _R) ^ x $ **, donc si vous le développez par le théorème binomial, ce sera comme suit.

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

Ici, en considérant la contribution d'un certain $ A \ _i $, ** $ A \ _i $ est une paire de $ (A \ _L, A \ _R) $ avec tous les nombres autres que lui-même **, donc ci-dessus En utilisant la formule, chaque terme développé par le théorème binomial est le suivant. (✳︎)

\_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})

De plus, s'il est implémenté tel quel, même si $ \ _xC \ _i $ est pré-calculé, $ x $ candidats sont $ k $, $ A \ _i $ candidats sont $ n $, et chacun des deux ci-dessus Le terme coefficient est $ x + 1 $, et le calcul dans $ () $ est $ n $ fois, il semble donc que même si vous le faites honnêtement, ce ne sera pas à temps. Par conséquent, pensons à ** résumer davantage les formules ** en partant du principe que certains ** pré-calculs **.

Autrement dit, considérons ** la somme de chaque coefficient binomial $ \ _xC \ _i $ pour tout $ A \ _i $ **. Ensuite, ce sera comme indiqué dans la figure ci-dessous.

Donc, si cette somme est mise ensemble, $ (A \ _1 ^ {xi} + A \ _2 ^ {xi} +… + A \ _n ^ {xi}) \ times (A \ _1 ^ {i} + A \ _2 ^ {i} +… + A \ _n ^ {i}) - (A \ _1 ^ {x} + A \ _2 ^ {x} +… + A \ _n ^ {x}) $ (** Symétrique Je pense que c'est naturel ** du point de vue du sexe).

Par conséquent, non seulement le pré-calcul du coefficient binomial, mais aussi le pré-calcul de $ y [i]: = (A \ _1 ^ i + A \ _2 ^ i +… + A \ _n ^ i) $ = i = 0 Si vous le faites avec $ ~ $ k $ ($ O (nk) $), vous pouvez trouver la somme à $ \ _xC \ _i $ avec $ O (1) $. Par conséquent, le montant total du calcul est $ O (k ^ 2) $ pour trouver la réponse pour chaque $ x $.

D'après ce qui précède, le montant total du calcul est $ O (n + nk + k ^ 2) = O (k (k + n)) $, ce qui est suffisamment rapide.

(✳︎)… A partir de là, on considère la condition de $ 1 \ leqq L, R \ leqq N, L \ neq R $ au lieu de $ 1 \ leqq L \ leqq n-1, L + 1 \ leqq R \ leqq n $. Cependant, il suffit de diviser par deux la réponse finale plutôt que la ** symétrie **.

D.cc

//Options de débogage:-fsanitize=undefined,address

//Optimisation du compilateur
#pragma GCC optimize("Ofast")

//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#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 est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 998244353 //10^9+7:Droit commun
#define MAXR 1000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire

template<ll mod> class modint{
public:
    ll val=0;
    //constructeur
    modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
    //Copier le constructeur
    modint(const modint &r){val=r.val;}
    //Opérateur arithmétique
    modint operator -(){return modint(-val);} //unaire
    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;}
    //Opérateur d'assignation
    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;
    }
    //Opérateur de comparaison d'équivalence
    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>;

//Flux d'E / S
istream &operator >>(istream &is,mint& x){//N'ajoutez pas de const à x
    ll t;is >> t;
    x=t;
    return (is);
}
ostream &operator <<(ostream &os,const mint& x){
    return os<<x.val;
}

//Puissance
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;
}

//Calcul du coefficient binomial
mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];
//Créer une table
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];
    }
}
//Partie calcul
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(){
    //Spécification de sortie du nombre de chiffres fractionnaires
    //cout<<fixed<<setprecision(10);
    //Code pour accélérer la saisie
    //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;
    }
}

Après le problème E