Critique du concours AtCoder pour débutant 177

Les résultats de cette fois

スクリーンショット 2020-08-30 8.12.01.png

Impressions de cette époque

J'ai pu passer à travers le problème D en douceur, mais même si E était facile, j'ai perdu ma concentration jusqu'au problème D. C'est une réflexion. Le problème F est un type de problème auquel je peux penser, mais je suis accro à la méthode de la solution du mensonge.

Problème A

Considérez s'il faut satisfaire $ t \ times s \ geqq d $.

A.py


n,x,t=map(int,input().split())
y=-((-n)//x)
print(y*t)

Problème B

$ len (s) \ times len (t) $ est d'environ 10 $ ^ 6 $, donc les candidats pour les sous-colonnes de $ s $ qui correspondent à $ t $ ($ len (s) -len (t) + 1 $ way) Tout ce que vous avez à faire est de rechercher.

B.py


s,t=input(),input()
ls=len(s)
lt=len(t)
ans=1000000000000
for i in range(ls-lt+1):
    ans_sub=0
    for j in range(lt):
        if t[j]!=s[i+j]:
            ans_sub+=1
    ans=min(ans,ans_sub)
print(ans)

Problème C

$ \ frac {(A \ _1 + A \ _2 +… + A \ _N) ^ 2- (A \ _1 ^ 2 + A \ _2 ^ 2 +… + A \ _N ^ 2)} {2} $ est la solution Je vais. C'est la politique parce que je veux trouver toutes les multiplications des deux nombres.

Normalement, cela semble être une politique de somme cumulative, mais je ne pense pas que ce soit une idée aussi difficile.

C.py


n=int(input())
a=list(map(int,input().split()))
x=sum(a)
y=sum([(a[i])**2 for i in range(n)])
print(((x**2-y)//2)%(10**9+7))

Problème D

Je soupçonne d'abord ** Union Find ** car il sera ** lié ** par l'amitié. En d'autres termes, les amis sont ceux qui sont inclus dans l'ensemble unis par une amitié donnée.

Maintenant, divisez les personnes $ N $ en aussi peu de groupes que possible afin de ne pas avoir d'amis dans le groupe. Ce nombre de groupes peut être supérieur ou égal au nombre maximum d'éléments dans chaque ensemble du système d'ensembles premiers, et ceci est produit.

De plus, en utilisant la bibliothèque de cet article, vous pouvez trouver la valeur maximale du tableau «size».

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 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;//Tableau associatif géré pour chaque ensemble premier(key est le parent de chaque ensemble premier, value est un tableau d'éléments de cet ensemble premier)

    //constructeur
    UnionFind(ll n):parent(n),siz(n,1){ 
        //Initialiser en tant que racine de tous les éléments est lui-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]);//La valeur de l'expression d'affectation étant 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éterminer 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(ll n){
        //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);
    }
};

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    UnionFind uf(n);
    REP(i,m){
        ll a,b;cin>>a>>b;
        uf.unite(a-1,b-1);
    }
    uf.grouping(n);
    ll ans=0;
    FORA(i,uf.group){
        ans=max(ans,SIZE(i.S));
    }
    cout<<ans<<endl;
}

E problème

Malgré son apparence, ce n'était pas difficile. Je veux me débarrasser de l'habitude d'avoir peur rien qu'en regardant.

Tout d'abord, nous devons gérer deux conditions ici. Le premier est que $ GCD (A \ _ i, A \ _ j) = 1 $ vaut pour tout $ 1 \ leqq i <j \ leqq N $. Dans le second cas, $ GCD (A \ 1, A \ 2,…, A \ N) = 1 $ tient. La deuxième condition est bonne car elle ne fait que $ O (N \ log {A {max}}) $, mais la première condition est $ O (N ^ 2 \ log {A {A { max}}) $.

Par conséquent, envisagez de reformuler davantage la première condition. Tout d'abord, ** arbitraire ** était difficile à gérer, donc compte tenu du refus, il y a au moins une paire de $ i, j $ qui devient $ GCD (A \ _i, A \ _j) \ neq 1 $. J'ai décidé de considérer ** s'il existe. A ce moment, quand il devient $ GCD (A \ _i, A \ _j) \ neq 1 $, il suffit de montrer que (pas 1) ** il existe une fraction commune **. Par conséquent, j'ai décidé d'énumérer les fractions de chaque $ A \ _i $ et de vérifier si les mêmes fractions existent. Cependant, cette méthode est difficile car la quantité de calcul est $ O (N \ sqrt {A \ _ {max}}) $ (il semble que cette méthode fonctionne également en C ++).

À ce stade, j'ai réalisé qu'il n'est pas nécessaire de lister toutes les fractions, mais uniquement les nombres premiers inclus dans la factorisation première **. En d'autres termes, si $ 12 = 2 \ fois 2 \ fois 3 $, $ 2,3 $ seront énumérés (cochés). A ce moment, il est possible d'effectuer une factorisation première avec $ O (\ log {A_ {i}}) $ par le tamis d'Eratostène, et le montant total du calcul est $ O (N \ log {A_ {i}}) $. Je vais.

À partir de ce qui précède, implémentez dans l'ordre suivant.

(1) Tableau PN_chk utilisé dans la factorisation des nombres premiers, tableau check pour vérifier combien de fois une fraction apparaît, dictionnaire (ou ensemble) pour vérifier le nombre qui apparaît dans chaque factorisation première $ A \ _i $ Préparez prime.

(2) Initialisez PN_chk à l'aide du tamis Eratostenes. Cela permet la factorisation des nombres premiers avec $ O (\ log {A_ {i}}) $.

③ Pour chaque $ A \ _i $, effectuez une décomposition en facteurs premiers et stockez-le dans prime. Les nombres premiers stockés sont enregistrés dans "check".

④ Vérifiez s'il y a 2 ou plus de chaque nombre premier enregistré dans «check». S'il y en a un, ce sera "setwise coprime" lorsque le pgcd total est de 1, et "pas coprime" quand ce n'est pas le cas. De plus, s'il n'y en a pas, ce sera "coprime par paires".

E.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 1000000 //10^6: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

#define PN 1 //La marque du nombre premier est 1

//MAXR(=10^6)Supposons que les nombres entiers jusqu'à sont des nombres premiers
vector<ll> PN_chk(MAXR+1,PN);//0index correspond au i-ème entier i(0~MAXR)


//O(MAXR)
void se(){
    ll MAXRR=sqrt(MAXR)+1;
    //Il se décompose en facteurs premiers de 2 nombres ou plus, de sorte qu'il peut être ignoré.
    PN_chk[0]=0;PN_chk[1]=0;
    FOR(i,2,MAXRR){
        //Un nombre premier s'il est supposé être un nombre premier à votre arrivée
        //Marquer un multiple d'un nombre premier car il est divisible par ce nombre premier
        if(PN_chk[i]==1) FOR(j,i,ll(MAXR/i)){PN_chk[j*i]=i;}
    }
}

vector<ll> check(MAXR+1,0);

//O(logn)
//Notez que prime n'est pas aligné dans ce cas! !! !!
//Contrôle unique
map<ll,ll> prime;

void prime_factorize(ll n){
    if(n<=1) return;
    //Si 1, n est un nombre premier
    if(PN_chk[n]==1){prime[n]+=1;return;}
    //Les nombres marqués sont des nombres premiers
    prime[PN_chk[n]]+=1;
    //Considérez le nombre de nombres marqués divisé par n
    prime_factorize(ll(n/PN_chk[n]));
}

signed main(){
    se();
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n;cin>>n;
    vector<ll> a(n);REP(i,n)cin>>a[i];
    //vérifier deux fois
    REP(i,n){
        prime_factorize(a[i]);
        FORA(j,prime){
            check[j.F]++;
        }
        prime.clear();
    }
    ll g=gcd(a[0],a[1]);
    FOR(i,2,n-1){
        g=gcd(g,a[i]);
    }
    REP(i,MAXR+1){
        if(check[i]>=2){
            if(g==1){
                cout<<"setwise coprime"<<endl;
            }else{
                cout<<"not coprime"<<endl;
            }
            return 0;
        }
    }
    cout<<"pairwise coprime"<<endl;
}

Problème F

Je ne pouvais pas du tout la passer pendant le concours, mais cela semblait être une meilleure politique que ce à quoi je m'attendais car il y avait un envoi ** que je pouvais restreindre les candidats.

Ce qui suit est une politique conforme à l'explication (je vais la résumer en réfléchissant à la façon d'y penser).

Tout d'abord, considérez si vous devez vous déplacer vers le bas ou vers la droite, mais lorsque vous vous déplacez vers la ligne $ k + 1 $, le nombre de fois pour descendre est toujours $ k $. Par conséquent, le nombre minimum de coups doit être considéré ** uniquement le nombre minimum de coups vers la droite ** (** séparation et simplification des opérations **).

De plus, lorsque vous vous déplacez à partir d'un certain point de départ, le nombre de fois où vous vous déplacez vers la droite est minimisé, donc lorsque vous pouvez descendre, vous devez descendre (** mouvement gourmand **). Par conséquent, on peut dire que ** une fois que le point de départ est déterminé, le point final est déterminé de manière unique **. De plus, vous devez aller vers la droite uniquement lorsque le point courant est inclus dans $ A \ _i $ à $ B \ _i $.

Par conséquent, tout en gérant les candidats (point final, point de départ), nous étudierons dans l'ordre à partir de la ligne du haut. De plus, à partir de la considération ci-dessus, le point final est déplacé vers $ B \ _ {i} + 1 $ uniquement lorsque le point final est inclus dans $ B \ _i $ de $ A \ _i $, mais s'il n'est pas inclus, le point final est déplacé. Il n'y a pas besoin de bouger. De plus, s'il y a plusieurs points de départ lors du déplacement du point final (car on veut trouver le cas où le nombre de mouvements est le minimum), ** seul le point de départ maximum doit être laissé **. De plus, si $ B \ _ {i} + 1 $ devient $ W $, il n'est pas nécessaire de mettre à jour les candidats (point final, point de départ).

De plus, pour trouver le cas où le point final est inclus dans $ A \ _i $ à $ B \ _i $, stockez l'ensemble de (point final, point de départ) dans set et utilisez lower_bound et ʻupper_bound`. C'est bon. De plus, s'il est inclus, le nombre d'éléments est réduit, mais ** le nombre total de réductions ne dépasse pas $ W $ **, donc le montant total du calcul est $ O ((H + W) \ log {(H +) W)}) $.

De plus, pour ** trouver le nombre minimum de mouvements dans chaque ligne à grande vitesse **, enregistrez la valeur du point final-point de départ avec ** multiset **, et faites la même chose que le jeu précédent`. Supprimer ou ajouter.

Par conséquent, la mise en œuvre est résumée comme suit.

① Préparez le coût de set à from, qui gère (point final, point de départ), et le coût de multiset, qui économise le nombre de mouvements (point final-point de départ).

② Initialisez à de et coût.

③ Effectuer des opérations sur chaque ligne

(1) Si $ [A \ _i, B \ _i] $ a un point final, déplacez le point final vers $ B \ _i + 1 $ et changez les deux en from et cost. En outre, il peut ne pas être nécessaire de le déplacer, alors faites attention à l'implémentation à ce moment-là. Ensuite, lorsque $ B \ _ {i} + 1 $ devient $ W $, insérez seulement dans cost sans insérer dans tofrom.

(2) Regardez le coût après l'opération de déplacement dans (1), et si le plus petit élément n'est pas INF, affichez cet élément, et si c'est INF, affichez -1.

Aussi, ** le problème que vous n'avez qu'à gérer une pièce avec set ou multiset en faisant attention à l'ordre de sélection ** et ** le problème qui gère les informations avec plusieurs structures de données ** sont difficiles. Je le vois souvent, donc je vais essayer de le garder comme une idée.


✳️ J'ai eu beaucoup de mal en termes de montage, je vais donc résumer quelques points ci-dessous.

① ** Une paire d'entiers peut être accélérée ** en les convertissant en entiers. (2) Lors de la recherche de l'intervalle avec lower_bound et upper_bound, cela provoquera un bug, il est donc préférable de suivre de ** lower_bound et de vérifier si la condition de l'extrémité supérieure est satisfaite **. ③ ** Si vous utilisez erase avec set ou multiset, l'itérateur suivant sera renvoyé **, il est donc très facile à implémenter si vous utilisez l'instruction while lors de l'implémentation de ③.

F.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 1000000 //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

signed main(){
    //Code pour accélérer la saisie
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll h,w;cin>>h>>w;
    //point final,Gérer le point de départ
    set<ll> tofrom;
    //Gérez le minimum
    multiset<ll> cost;
    REP(i,w){
        tofrom.insert(i*MOD+i);
        cost.insert(0);
    }
    REP(i,h){
        ll a,b;cin>>a>>b;a--;b--;
        auto j=tofrom.lower_bound(a*MOD);
        if(j!=tofrom.end()){
            ll ne=-1;
            while(j!=tofrom.end() or *j<(b+2)*MOD){
                cost.erase(cost.lower_bound(ll(*j/MOD)-*j%MOD));
                ne=*j%MOD;
                j=tofrom.erase(j);
            }
            if(b==w-1){
                cost.insert(INF);
            }else{
                cost.insert(b+1-ne);
                tofrom.insert((b+1)*MOD+ne);
            }
        }
        if(*cost.begin()!=INF)cout<<*cost.begin()+i+1<<"\n";
        else cout<<-1<<"\n";
    }
}

Recommended Posts

Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
Critique du concours AtCoder
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 181 Remarque
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
Concours AtCoder Débutant 180 Remarque
Concours AtCoder Débutant 182 Remarque
AtCoder Grand Contest 048 Critique
Concours AtCoder pour débutants 156 WriteUp
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Concours AtCoder pour débutants 167
Concours AtCoder Débutant 183 Remarque
AtCoder Regular Contest 106 Évaluation
Concours AtCoder Débutant 184 Remarque
AtCoder Grand Contest 046 Critique
Revue du concours régulier AtCoder 104
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes