[PYTHON] AtCoder Beginner Contest 097 Revue des questions précédentes

Temps requis

スクリーンショット 2020-04-06 10.31.45.png

Impressions

Je n'ai pas pu le résoudre pendant le concours car d'autres courses se sont inscrites pendant le concours. De plus, j'ai beaucoup de critiques sur ABC, donc je ne ferai pas de nouveau bachacon aujourd'hui demain. Le FX que je fais maintenant n'a pas été coupé, alors j'aimerais garder les choses organisées.

Problème A

Vous n'avez qu'à décider si vous pouvez parler directement ou indirectement.

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

Problème B

De tels problèmes liés à la multiplication et à la division ont émis plusieurs fois WA même si des erreurs sont susceptibles de se produire. Pour de tels problèmes, je voudrais faire attention à séparer les cas aux limites et éviter d'utiliser des fonctions telles que le plafond, le sol et le journal.

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

Problème C

Le K-ième plus petit est calculé dans l'ordre du dictionnaire, mais l'ordre du dictionnaire est calculé par ** ordre alphabétique ** et ** longueur **. Au début, j'ai écrit le code en se concentrant sur ** l'ordre alphabétique ** et TLE, mais quand j'y ai ajouté la contrainte ** length **, j'ai pu 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])

Problème D

Je n'ai pas pu le résoudre car j'avais quelque chose à faire pendant le bachacon, mais ce n'était pas si difficile. ** Il y avait un sentiment que les éléments qui peuvent être remplacés (peuvent subir plusieurs remplacements) peuvent être remplacés sans remplacer d'autres éléments **, donc je l'ai passé sans preuve ( ✳︎ 1). ** Je pense qu'il est difficile de faire des choses non certifiées sur une base régulière **, donc je le regrette. En supposant que cela est correct, créez un arbre Union-Find ** dont l'ensemble principal est un ensemble contenant des éléments remplaçables, puis utilisez la fonction de regroupement pour séparer chaque ensemble premier. Si le traitement jusqu'à ce point peut être effectué, le reste doit être considéré lorsque $ p_i = i $ vaut autant que possible pour les éléments contenus dans chaque ensemble premier. Ici, puisque l'ensemble premier contient la valeur d'index, il peut être obtenu en ** prenant l'ensemble des produits (partie commune) de l'ensemble premier et l'ensemble des éléments de p dont l'indice est cet élément **. .. Pour l'ensemble de produits, set_intersection est effectué avec l'ensemble souhaité comme argument, et la longueur totale de l'ensemble de produits est calculée pour chaque ensemble premier pour trouver la valeur maximale de i telle que $ p_i = i $. (✳︎2)

(✳︎1)… La preuve mathématique est écrite dans Answer, donc je vais l'ignorer, mais la preuve sensuelle est la suivante. Je vais.

IMG_0181.JPG

(✳︎2)… Pour savoir comment utiliser set_intersection, je me suis référé à ce blog.

answerD.cc


//Référence: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Comprendre
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable
#include<iterator>//set_intersection,set_union,set_En raison de la différence

using namespace std;
typedef long long ll;

//macro
#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() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à 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:Portée maximale(Utilisé pour l'énumération des nombres premiers, etc.)

//Référence: https://pyteyon.hatenablog.com/entry/2019/03/11/200000
//Référence: https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396

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;

    //Du constructeur:Derrière l'initialisation des variables membres
    UnionFind(ll n):parent(n),siz(n,1){ //Initialisez car tout est root au début
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    ll root(ll x){ //Récupère la racine de l'arbre auquel les données x appartiennent de manière récursive
        if(parent[x]==x) return x;
        //La valeur de l'expression d'affectation sera la valeur de la variable affectée!
        //Compression de chemin(Rationalisez les calculs en connectant les éléments directement à la racine)
        return parent[x]=root(parent[x]);
        //Mettre à jour le parent lors de l'obtention par récursif
    }

    void unite(ll x,ll y){ //Fusionner les arbres x et y
        ll rx=root(x);//La racine de x est rx
        ll ry=root(y);//y root ry
        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
    }

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

    ll size(ll x){ //Taille de l'ensemble élémentaire
        return siz[root(x)];
    }

    void grouping(ll n){ //Regroupement d'ensembles élémentaires
        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));
        //N'oubliez pas de trier
        set_intersection(ALL(value),ALL(value2),back_inserter(vecinter));
        //cout << ans << endl;
        ans+=vecinter.size();
        //cout << endl;
    }
    cout << ans << endl;
}

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 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 054 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes
AtCoder Beginner Contest 122 Revue des questions précédentes