[PYTHON] AtCoder Débutant Contest 170 Critique
Les résultats de cette fois
Impressions de cette époque
J'ai fait une grosse erreur après un long moment. Je ne pensais pas que D ne passerait pas, mais si vous réfléchissez calmement, vous ne pouvez pas le passer avec Python ou PyPy en termes de volume de calcul ... J'ai résolu E dans la seconde moitié, mais ça fait mal d'avoir un bug dans l'implémentation ... La rapidité de mise en œuvre semble devoir être entraînée à plusieurs reprises pour s'y habituer.
Quand je jouais au golf codé, j'étais en retard pour publier un article. J'essaierai de jouer au code golf après avoir terminé l'examen ...
Problème A
Puisqu'il s'agit d'une chaîne entière après la substitution de 0, l'index de l'élément qui devient 0 peut être calculé par 1-indexed.
A.py
x=list(map(int,input().split()))
print(x.index(0)+1)
Problème B
Considérez combien d'animaux sont respectivement des grues et des tortues. Il y a 0 à x grues et tortues, et si vous décidez combien d'entre elles sont, l'autre sera décidée, et si vous savez combien d'entre elles, le nombre de pattes sera décidé, alors cherchez une combinaison qui sera y.
B.py
x,y=map(int,input().split())
for i in range(x+1):
if 2*i+4*(x-i)==y:
print("Yes")
break
else:
print("No")
Problème C
Récemment, j'ai le sentiment qu'il y a des problèmes à prendre en compte chez C.
Calcul d'un entier
C.py
x,n=map(int,input().split())
p=sorted(list(map(int,input().split())))
q=[0]*(102)
for i in range(n):
q[p[i]]=1
ans=(1000000,-1)
for i in range(102):
if q[i]==0:
if ans[0]>abs(i-x):
ans=(abs(i-x),i)
print(ans[1])
Problème D
Il a été écrit dans la Réponse que cela peut être fait par la même opération que le tamis Eratostenes, mais j'ai été forcé à $ O (N \ sqrt { A_ {max}}) Je l'ai passé avec $. Puisque la quantité de calcul est à peine suffisante pour Python et PyPy, je l'ai changé en C ++. De plus, je n'ai pas pu prendre cette décision pendant le concours, alors j'ai senti que je devais être ** calme. ** Lorsque $ A_i $ est divisible par $ A_j $, $ A_j $ est une fraction de $ A_i $ **. De plus, comme vous pouvez le voir dans cet article, vous pouvez énumérer les fractions avec $ O (\ log {A_i}) $. Par conséquent, il est possible d'énumérer les fractions pour chaque $ A_i $ et de déterminer que les propriétés de l'énoncé du problème ne sont pas satisfaites si les fractions sont incluses dans la séquence $ A $.
Comme note supplémentaire, quand j'ai regardé le commentaire de M. Maspy, j'ai pensé qu'il était vrai qu'il était écrit que ** il est plus facile de trouver des multiples que des fractions dans l'ordre des relations **. Je veux l'utiliser à partir de maintenant.
D.cc
//Comprendre(Ordre alphabétique)
#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<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#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
using namespace std;
typedef long long ll;
//macro
//pour la relation de 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.
#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--)
//x est un conteneur tel que vector
#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)) //Trouvez la valeur maximale
#define MIN(x) *min_element(ALL(x)) //Trouvez la valeur minimale
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#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
vector<ll> make_divisors(ll n){
vector<ll> divisors;
//cout << 1 << endl;
FOR(i,1,ll(sqrt(n))){
if(n%i==0){
divisors.PB(i);
if(i!=ll(n/i))divisors.PB(ll(n/i));
}
}
return divisors;
}
signed main(){
ll n;cin >> n;
map<ll,ll> a;
REP(i,n){
ll x;cin >> x;
a[x]+=1;
}
ll ans=0;
for(auto i=a.begin();i!=a.end();i++){
vector<ll> div=make_divisors(i->F);
//cout << 1 << endl;
ll f=true;
REP(j,SIZE(div)){
if((a.find(div[j])!=a.end() and div[j]!=(i->F))or(div[j]==(i->F) and (i->S)>1)){
f=false;
break;
}
}
if(f)ans++;
}
cout << ans << endl;
}
E problème
Le multiset que j'ai fait la semaine dernière est sorti, mais je n'ai pas pu le résoudre à cause d'un bug dans l'implémentation ...
Tout d'abord, ** vous devez stocker le tout-petit avec le taux le plus élevé dans chaque jardin **, alors préparez un récipient pour le stocker (youjitati). De plus, ** le bébé à taux le plus élevé dans chaque jardin doit également être stocké dans un conteneur ** (youtien), mais ** les éléments yojitati et yotien peuvent changer en fonction du changement de jardin **, donc seul le bébé à taux le plus élevé Au lieu de **, vous devez stocker à la fois youjitati et youtien sous forme de conteneurs triés **.
Ici, ** C ++ set, multiset ** sont disponibles sous forme de ** conteneurs ** qui peuvent être ajoutés ou supprimés à grande vitesse tout en conservant l'état trié ($ O (\ log {n}) $) (Python). Il y a aussi une file d'attente en tas, mais il me semble que c'est difficile à utiliser personnellement, contrairement à mon intuition.) De plus, ici, j'ai décidé d'utiliser un multiset qui stocke le taux et le nombre du bébé par paire pour distinguer les nourrissons avec le même taux, mais comme il peut être distingué par appariement, le résultat est le même pour les ensembles au lieu du multiset Vous pouvez écrire un programme comme celui-ci.
Par conséquent, si vous organisez ce qui précède, youjitati enregistre le taux de nourrissons le plus élevé dans chaque jardin d'enfants dans la paire <taux infantile, nombre infantile> dans l'ordre croissant avec multiset <paire <ll, ll >>, et youtien Enregistre les taux de chaque enfant de la maternelle dans l'ordre croissant avec vector <multiset <pair <ll, ll >>>.
Envisagez de traiter chaque requête sous celle-ci. Ici, nous envisagerons de transférer l'enfant C de la maternelle E à la maternelle D, mais ** la maternelle E à laquelle appartient l'enfant C ne peut pas être comprise à partir des conteneurs youjitati et youtien mentionnés précédemment **. Par conséquent, enregistrez simplement ** dans quel jardin d'enfants se trouve chaque enfant ** dans vector <ll> (doko). Sur cette base, pensons au traitement des requêtes avec des diagrammes.
Tout d'abord, considérons le cas où vous avez suffisamment de bambins. Ici, il est facile de comprendre s'il est divisé en ** étapes , et il peut être divisé en trois étapes. ( Je n'ai pas pu organiser la production jusqu'à présent . Je pense que je dois gagner en confiance car je peux le résoudre si je me calme.)
① effacer de youjitati
Tout d'abord, il est nécessaire d'effacer une fois le taux maximum des nourrissons de la maternelle D et de la maternelle E stockés dans youjitati car les éléments à stocker dans youjitati peuvent changer lors du déplacement du bébé C. Ici, le taux maximum des nourrissons de la maternelle D et de la maternelle E peut être obtenu dans l'itérateur comme --youtien [D] .end (), --youtien [E] .end (). ( C'est rafraîchissant de penser que vous devriez vous échapper une fois **.)
② Mouvement de l'enfant C
À la fin de ①, déplacez le bébé C de la maternelle E à la maternelle D. À ce stade, lorsque vous recherchez l'élément de l'enfant C, vous devez rechercher par <taux infantile, nombre enfant>, et ** le taux infantile ne peut pas être obtenu tel quel **, donc chaque taux infantile est vecteur. Enregistrez-le dans <ll> (tikara). Cela permet à l'opération de déplacement de l'enfant C d'être facilement exprimée en effaçant de youtien [E] et en l'insérant dans youtien [D].
③ insérer dans youjitati
J'ai effacé de youjitati au stade de ① plus tôt, mais cette fois, il est nécessaire de réinsérer. Ce n'est pas difficile. Comme dans le cas de ①, vous pouvez obtenir le taux maximum de nourrissons à la maternelle D et à la maternelle E avec --youtien [D] .end (), --youtien [E] .end (), alors insérez-les. C'est bon.
De plus, c'est ** s'il y a suffisamment de tout-petits dans youtien , et qu'il n'y a peut-être pas assez de tout-petits à effacer. Dans ce cas, il est bon de diviser le cas comme indiqué dans le code ci-dessous, mais si la taille de ** youtien [E] et youutien [D] est 0, vous pouvez simplement ne pas opérer ** J'ai réalisé plus tard que ( la simplification de tels problèmes est très importante **).
Répétez l'opération ci-dessus pour chaque requête, obtenez le plus petit élément avec youjitati avec youjitati.begin () et affichez-le.
E.cc
//Comprendre(Ordre alphabétique)
#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<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#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
using namespace std;
typedef long long ll;
//macro
//pour la relation de 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.
#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--)
//x est un conteneur tel que vector
#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)) //Trouvez la valeur maximale
#define MIN(x) *min_element(ALL(x)) //Trouvez la valeur minimale
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#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 f=2*pow(10,5);
ll n,q;cin >> n >> q;
vector<multiset<pair<ll,ll>>> youtien(f);
vector<ll> doko(n);
vector<ll> tikara(n);
REP(i,n){
ll a,b;cin >> a >> b;b--;
youtien[b].insert(MP(a,i));
doko[i]=b;
tikara[i]=a;
}
multiset<pair<ll,ll>> youjitati;
REP(i,f){
if(!(youtien[i].empty())){
youjitati.insert(*(--youtien[i].end()));
}
}
REP(i,q){
ll c,d;cin >> c >> d;c--;d--;
if(youtien[d].size()>0 and youtien[doko[c]].size()>1){
youjitati.erase(*(--youtien[d].end()));
youjitati.erase(*(--youtien[doko[c]].end()));
youtien[d].insert(MP(tikara[c],c));
youtien[doko[c]].erase(MP(tikara[c],c));
youjitati.insert(*(--youtien[d].end()));
youjitati.insert(*(--youtien[doko[c]].end()));
doko[c]=d;
}else if(youtien[d].size()==0 and youtien[doko[c]].size()>1){
youjitati.erase(*(--youtien[doko[c]].end()));
youtien[d].insert(MP(tikara[c],c));
youtien[doko[c]].erase(MP(tikara[c],c));
youjitati.insert(*(--youtien[d].end()));
youjitati.insert(*(--youtien[doko[c]].end()));
doko[c]=d;
}else if(youtien[d].size()>0 and youtien[doko[c]].size()==1){
youjitati.erase(*(--youtien[doko[c]].end()));
youjitati.erase(*(--youtien[d].end()));
youtien[d].insert(MP(tikara[c],c));
youtien[doko[c]].erase(MP(tikara[c],c));
youjitati.insert(*(--youtien[d].end()));
doko[c]=d;
}else{
youjitati.erase(*(--youtien[doko[c]].end()));
youtien[d].insert(MP(tikara[c],c));
youtien[doko[c]].erase(MP(tikara[c],c));
youjitati.insert(*(--youtien[d].end()));
doko[c]=d;
}
cout << (youjitati.begin())->F << endl;
}
}
Problème F
Je peux penser à BFS et DFS ** car il n'y a pas ** de recherche et de pondération sur les carrés du nombre de $ H \ fois W \ leqq 10 ^ 6 $. De plus, comme c'est le nombre minimum de coups, je vais chercher avec BFS **.
Tout d'abord, considérez tous les candidats possibles pour la prochaine masse à tracer par chaque récursif. En d'autres termes, considérez les rues 4K qui avancent de K carrés dans quatre directions, vers le haut, le bas, la gauche et la droite, ce qui peut être le carré suivant (cependant, dans le cas de @ square, vous ne pouvez pas aller au-delà). Cependant, si vous recherchez tout cela, vous constaterez que vous cherchez trop ** (même si vous ne savez pas que vous cherchez trop, vous le remarquerez lorsque vous TLE). Par conséquent, vous devez considérer ** la condition de masse minimale ** pour une recherche nécessaire et suffisante.
Ici, quand je pense réellement à la recherche précédente dans mon esprit, j'ai implémenté BFS, qui est le TLE, par la méthode ** de sauter les cellules déjà recherchées et de suivre les cellules K **. J'ai senti qu'il y avait un gaspillage en termes de re-recherche des carrés qui avaient déjà été fouillés **. En d'autres termes, puisqu'il est possible de rechercher du carré déjà recherché à K carrés dans quatre directions, les carrés déjà recherchés ont déjà été recherchés. Par conséquent, j'ai considéré que s'il y a une cellule qui a déjà été recherchée en plus de la cellule de @, la recherche après cela se terminera. Ceci est illustré ci-dessous.
Cependant, tel quel, il n'est pas possible de considérer les carrés qui ont été recherchés mais la recherche au-delà de ce carré n'a pas commencé. On peut dire que ces cellules sont des ** cellules de même profondeur **, et s'il y a de telles cellules, la recherche se poursuivra. Ceci est illustré ci-dessous.
Compte tenu de ce qui précède, vous pouvez facilement l'implémenter en le considérant comme un type légèrement différent de BFS, et le code sera le suivant.
F.py
import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque([[x1-1,y1-1]])
dp[x1-1][y1-1]=0
def bfs(d):
global dp,now
l=len(now)
dp_sub=deque()
cand=set()
for i in range(l):
x,y=now.popleft()
for j in range(1,min(k+1,w-y)):
if dp[x][y+j]==inf:
dp_sub+=[[x,y+j,d]]
cand.add((x,y+j))
else:
break
for j in range(1,min(k+1,y+1)):
if dp[x][y-j]==inf:
dp_sub+=[[x,y-j,d]]
cand.add((x,y-j))
else:
break
for j in range(1,min(k+1,h-x)):
if dp[x+j][y]==inf:
dp_sub+=[[x+j,y,d]]
cand.add((x+j,y))
else:
break
for j in range(1,min(k+1,x+1)):
if dp[x-j][y]==inf:
dp_sub+=[[x-j,y,d]]
cand.add((x-j,y))
else:
break
while dp_sub!=deque([]):
e=dp_sub.popleft()
dp[e[0]][e[1]]=e[2]
for i in cand:
now+=[i]
if l!=0:bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
answerF.cc
//Comprendre(Ordre alphabétique)
#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<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#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
using namespace std;
typedef long long ll;
//macro
//pour la relation de 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.
#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--)
//x est un conteneur tel que vector
#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)) //Trouvez la valeur maximale
#define MIN(x) *min_element(ALL(x)) //Trouvez la valeur minimale
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#define MP make_pair //constructeur de paires
#define PF pop_front
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire
ll h,w,k;
vector<vector<ll>> dp;
deque<pair<ll,ll>> now;
void bfs(ll d){
ll l=SIZE(now);
if(l==0){
return;
}
deque<vector<ll>> dp_sub;
set<pair<ll,ll>> cand;
REP(i,l){
ll x,y;x=now.front().F;y=now.front().S;now.PF();
FOR(j,1,min(k,w-y-1)){
if(dp[x][y+j]==INF){
dp_sub.PB({x,y+j,d});
//dp[x][y+j]=d;
cand.insert(MP(x,y+j));
//now.PB(MP(x,y+j));
}else{
break;
}
//if(dp[x][y+j]==-1)break;
}
FOR(j,1,min(k,y)){
if(dp[x][y-j]==INF){
dp_sub.PB({x,y-j,d});
//dp[x][y-j]=d;
cand.insert(MP(x,y-j));
//now.PB(MP(x,y-j));
}else{
break;
}
//if(dp[x][y-j]==-1)break;
}
FOR(j,1,min(k,h-x-1)){
if(dp[x+j][y]==INF){
dp_sub.PB({x+j,y,d});
//dp[x+j][y]=d;
cand.insert(MP(x+j,y));
//now.PB(MP(x+j,y));
}else{
break;
}
//if(dp[x+j][y]==-1)break;
}
FOR(j,1,min(k,x)){
if(dp[x-j][y]==INF){
dp_sub.PB({x-j,y,d});
//dp[x-j][y]=d;
cand.insert(MP(x-j,y));
//now.PB(MP(x-j,y));
}else{
break;
}
//if(dp[x-j][y]==-1)break;
}
}
while(!dp_sub.empty()){
vector<ll> d=dp_sub.front();
dp[d[0]][d[1]]=d[2];
dp_sub.PF();
}
for(auto i=cand.begin();i!=cand.end();i++){
now.PB(*i);
}
bfs(d+1);
}
signed main(){
//Code pour accélérer la saisie
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> h >> w >>k;
ll x1,y1,x2,y2;cin >> x1 >> y1 >> x2 >> y2;
vector<string> c(h);REP(i,h)cin >> c[i];
dp.resize(h);
REP(i,h){
REP(j,w){
if(c[i][j]=='.')dp[i].PB(INF);
else dp[i].PB(-1);
}
}
now.PB(MP(x1-1,y1-1));
dp[x1-1][y1-1]=0;
bfs(1);
if(dp[x2-1][y2-1]!=INF) cout << dp[x2-1][y2-1] << endl;
else cout << -1 << endl;
}
Recommended Posts