[PYTHON] Critique du concours AtCoder pour débutant 177
Les résultats de cette fois
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