[PYTHON] Codeforces Round # 612 (Div.2) Examen Bacha (10/2)
Les résultats de cette fois
Impressions de cette époque
Cette fois, ** je ne pouvais pas comprendre le problème à jeter **, et ** j'étais submergé par l'apparence du jeu d'implémentation **.
De plus, je ne pouvais pas déboguer ** du point de vue de la question de savoir s'il y a un problème de considération ou d'implémentation, donc je vais l'utiliser avec le yukicoder d'aujourd'hui.
Problème A
** J'ai mal lu ce qui devrait être sorti au début **.
Changez la personne à côté de A en A à chaque fois et répétez ceci jusqu'à ce que cela ne change pas, et à chaque fois au moins une personne changera en A, alors écrivez un programme avec le stupide $ O (N ^ 2) $ peut faire.
A.py
for _ in range(int(input())):
n=int(input())
s=[i=="A" for i in list(input())]
tim=[s]
ans=0
while True:
t=[s[0]]
for i in range(n-1):
if tim[-1][i]==1:
t.append(True)
else:
t.append(tim[-1][i+1])
#print(s,t)
if tim[-1]==t:
break
ans+=1
tim.append(t)
#print(s,t)
print(ans)
Problème B
C'était le problème le plus difficile que j'ai résolu cette fois. Si vous n'écrivez pas un programme efficace, il sera supprimé par un multiple constant. Je regrette de n'avoir généralement pas eu autant de conscience.
(Dans ce qui suit, la discussion implique la condition que ** aucune carte n'a les mêmes caractéristiques **.)
Tout d'abord, je voulais regarder chaque fonctionnalité une par une par récursivité, mais c'est difficile car chaque fonctionnalité ne peut pas être considérée indépendamment. Je suis coincé ici, mais si je regarde le problème calmement, j'ai atteint la ligne où $ O (KN ^ 3) $ peut être idiot, et $ N $ est d'environ 1500 au maximum, donc $ O (N ^ 2) J'ai remarqué qu'un programme d'environ $ serait à temps (** Si vous êtes coincé dans une politique, envisagez une solution simple! **).
Par conséquent, envisagez de choisir deux cartes. Ensuite, vous pouvez voir que ** les cartes restantes sont déterminées de manière unique **. En d'autres termes, pour une certaine caractéristique, si les deux cartes décidées sont égales, les cartes restantes sont égales, et si les deux cartes décidées sont différentes, la carte restante est également une autre caractéristique. Par conséquent, vous devez considérer ** si les cartes restantes sont incluses dans la carte donnée . De plus, si la carte donnée est sauvegardée dans la structure d'ensemble, $ O (k \ log {n}) $ sera utilisé pour déterminer si elle est incluse dans $ O (k) $ pour trouver les cartes qui peuvent être combinées. Donc, si vous l'assemblez, vous pouvez l'implémenter avec $ O (k \ log {n}) $. Par conséquent, le montant total du calcul est $ O (n ^ 2k \ log {n}) $, et $ n ^ 2k \ log {n} $ est d'environ 10 $ ^ 8 $ ~ 10 $ ^ 9 $ au maximum. Même en C ++, c'est à peine suffisant, alors " alléger le jugement **", "car c'est trois caractères $ S, E, T $, ** le convertir en un nombre ternaire (facile à implémenter s'il s'agit d'un nombre quaternaire) ** , "Si vous demandez un jeu de trois cartes, elles seront dupliquées, mais à ce stade, il vous sera demandé trois fois la réponse, donc ** pas besoin de juger les doublons **, (le nombre de choses qui remplissent les conditions) $ \ div 3 $ Si vous utilisez "Good thing", vous pouvez accélérer d'un certain nombre de fois, et vous pouvez le passer avec une marge (732ms $).
✳︎… set et map peuvent être insérés avec $ O (\ log {n}) $, mais ** certains éléments ne sont pas $ O (\ log {n}) $ ** La prudence est de mise. Par exemple, une chaîne d'une longueur de $ l $ sera ralentie par la longueur de la chaîne, $ O (l \ log {n}) $. Par conséquent, lorsque vous traitez avec une chaîne de caractères comme celle-ci, vous devez être prudent dans l'analyse de la quantité de calcul.
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
ll k;
vector<ll> cards;
//Renvoie le i-ième nombre
inline ll quadrant(ll x,ll i){
return ((x>>(2*i))&1)+((x>>(2*i+1))&1)*2;
}
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n>>k;
//Convertissez le vecteur en quaternaire!(Nombre binaire réel)
cards=vector<ll>(n);
map<ll,ll> ma;
vector<ll> po(k);
REP(i,k)po[i]=1LL<<(2*i);
REP(j,n){
string s;cin>>s;
ll calc=0;
REP(i,k){
if(s[i]=='S'){
calc+=1*po[i];
}else if(s[i]=='T'){
calc+=2*po[i];
}else{
calc+=3*po[i];
}
}
cards[j]=calc;
ma[cards[j]]=j;
}
//Arrêtez de gérer les candidats avec cand(Divisez simplement par 3)
//Taille?
ll ans=0;
REP(i,n){
FOR(j,i+1,n-1){
ll ne=0;
REP(l,k){
ll temp=quadrant(cards[i],l)*quadrant(cards[j],l);
if(temp==1 or temp==6){
ne+=po[l];
}else if(temp==3 or temp==4){
ne+=2*po[l];
}else{
ne+=3*po[l];
}
}
if(ma.find(ne)!=ma.end()){
ans++;
}
}
}
cout<<ll(ans/3)<<endl;
}
Problème C
Même s'il s'agit d'un DP, la mise en œuvre est devenue lourde. C'est mauvais ...
Tout d'abord, étant donné que $ n $ vaut 100, lisez l'énoncé du problème en tenant compte de ** $ O (n ^ 3) $. De plus, la complexité est déterminée par ** combien de nombres adjacents ont des valeurs et des cotes différentes **, alors considérez ** décider dans l'ordre à partir de l'avant **. De plus, comme seulement 1 ~ $ n $ sort, ** seules les cotes et les cotes doivent être connues **, $ [\ frac {n} {2}] $ pair et $ n - [\ frac {n } {2}] Alignez simplement $ cotes.
Ici, il est ** difficile de décider avec gourmandise ** en décidant dans l'ordre de l'avant, mais quand vous regardez l'élément $ i $ ème, combien de ** pair et impair sont utilisés jusqu'à ce point ** et ** Je n'ai pas trouvé difficile de trouver la complexité minimale si je conservais la régularité ** du dernier élément. Vous pouvez également voir facilement que ce DP est $ O (n ^ 3) $. Par conséquent, définissez le DP comme suit.
$ dp [i] [j] [k]: = $ (Détermine jusqu'au $ i $ ème élément, n'utilise que $ j $ pair, et divise le $ i $ ème élément par 2 pour obtenir le reste de $ k $ Complexité temporelle minimale)
Par conséquent, en considérant la transition de $ p [i-1] $ à $ p [i] $, cela devient comme suit. De plus, la transition devrait prendre $ min $ au lieu de $ = $, mais elle est écrite comme ceci pour ne pas être redondante.
(1) Quand $ p [i]! = 0 $ et $ p [i] $ est pair
Lorsque $ p [i-1] $ est pair, la régularité ne change pas, donc $ dp [i] [j + 1] [0] = dp [i-1] [j] [k] $.
Quand $ p [i-1] $ est impair, la régularité change, donc $ dp [i] [j + 1] [0] = dp [i-1] [j] [k] + 1 $.
(2) Quand $ p [i]! = 0 $ et $ p [i] $ est impair
Lorsque $ p [i-1] $ est impair, la régularité ne change pas, donc $ dp [i] [j + 1] [1] = dp [i-1] [j] [k] $.
Quand $ p [i-1] $ est pair, la régularité change, donc $ dp [i] [j + 1] [1] = dp [i-1] [j] [k] + 1 $.
(3) Lorsque $ p [i] = 0 $
Puisque $ p [i] $ peut avoir n'importe quel nombre de cotes et de cotes, il suffit de combiner les transitions de (1) et (2).
À partir de ce qui précède, la transition peut être considérée et la valeur finale à obtenir est la valeur minimale lorsque ** $ i = n-1, j = n // 2 $ **, donc $ min (dp [-1] [ n // 2]) Il suffit de sortir $.
C.py
n=int(input())
p=list(map(int,input().split()))
inf=10**12
dp=[[[inf,inf] for j in range(101)] for i in range(n)]
if p[0]!=0:
if p[0]%2==0:
dp[0][1][0]=0
else:
dp[0][0][1]=0
else:
dp[0][1][0]=0
dp[0][0][1]=0
for i in range(1,n):
for j in range(101):
for k in range(2):
if dp[i-1][j][k]==inf:
continue
if p[i]!=0:
if p[i]%2==0:
if k==0:
dp[i][j+1][0]=min(dp[i-1][j][k],dp[i][j+1][0])
else:
dp[i][j+1][0]=min(dp[i-1][j][k]+1,dp[i][j+1][0])
else:
if k==0:
dp[i][j][1]=min(dp[i-1][j][k]+1,dp[i][j][1])
else:
dp[i][j][1]=min(dp[i-1][j][k],dp[i][j][1])
else:
if k==0:
dp[i][j+1][0]=min(dp[i-1][j][k],dp[i][j+1][0])
else:
dp[i][j+1][0]=min(dp[i-1][j][k]+1,dp[i][j+1][0])
if k==0:
dp[i][j][1]=min(dp[i-1][j][k]+1,dp[i][j][1])
else:
dp[i][j][1]=min(dp[i-1][j][k],dp[i][j][1])
print(min(dp[-1][n//2]))
Problème D
Cette fois, il y avait de nombreux problèmes avec une mise en œuvre relativement lourde. Cependant, je ne pense pas que l'idée elle-même soit si tordue. Je pense que ce sera fort si je peux écrire ceci innocemment, alors je ferai de mon mieux.
Dans ce qui suit, les sommets du sous-arbre sont implicitement exprimés comme $ a \ _j $ sauf pour $ a \ _i $ contenu dans le sous-arbre dont les sommets sont $ a \ _i $ et $ a \ _i $. Veuillez me pardonner pour simplifier l'explication.
Configurez $ a \ _i $ de sorte que seul $ c \ _i $ existe pour un sommet $ i $ qui est inférieur au nombre $ a \ _i $ écrit en lui-même parmi ses éléments de sous-arbre. pense. Ici, il va de soi que ** résoudre en utilisant DFS car nous avons besoin d'informations sur le sous-arbre **. De plus, pour l'apex de la feuille, si $ c \ _i = 0 $, vous pouvez définir $ a \ _i = 1 $, et si $ c \ _i> 0 $, c'est impossible, vous pouvez donc afficher NON. .. De plus, ** si le sommet $ i $ n'est pas une feuille, il est nécessaire de fusionner plusieurs sous-arbres avec son enfant comme sommet **, mais lors de la fusion, $ a \ _j $ a été mis ensemble dans un tableau. Trier sur. Sous cette source, nous insérerons $ a \ _i $ dans ce tableau, mais comme il est trié, nous l'insérerons comme valeur entre l'élément ** $ c \ _i-1 $ ème et l'élément $ c \ _i $ ème * *est nécessaire. De plus, s'il y a une différence de plus de 1 entre l'élément $ c \ _i-1 $ th et l'élément $ c \ _i $ th, il n'est inséré qu'entre eux, mais s'ils sont égaux, le $ c \ _i + 1 $ th et les éléments suivants sont insérés. Vous devez ajouter +2 à l'élément avant de l'insérer. De plus, ** Veillez à ne pas rompre la relation de grandeur de $ a \ _j $ dans le sous-arbre que vous avez déjà obtenu **.
Compte tenu des considérations ci-dessus, la politique de base est parfaite, mais je vais également aborder la mise en œuvre. Comme il n'est pas difficile de créer un arbre en supposant un graphe adjacent dirigé et que la sortie n'est pas difficile, nous ne considérerons que l'implémentation de DFS.
Tout d'abord, nous devons renvoyer un tableau de valeurs $ a \ _j $ dans un sous-arbre fixe aux sommets parents. De plus, dans la sortie finale, il est nécessaire de ** correspondre à l'index de chaque sommet **, de sorte que la valeur de retour est renvoyée au tableau de paires (valeur, index).
Ici, préparez $ ret $ comme un tableau qui stocke les informations arbitraires de $ a \ _j $. Dans ce $ ret $, vous pouvez insérer les éléments du tableau retourné par dfs avec les sommets enfants comme sous-arbres. Après l'insertion, triez (par ordre croissant de valeur).
Ensuite, envisagez de déterminer $ a \ _i $ à partir de $ ret $. De plus, il convient de noter que ** peut ne pas tenir en premier lieu **.
① Quand $ c \ _i > (nombre total de a \ _j $) Puisque $ a \ _i $ qui satisfait cette condition n'existe pas, vérifiez-le comme non valide. La valeur de retour doit être un tableau vide.
② Quand $ c \ _i \ = (nombre total de a \ _j $) ** Insérez le plus grand élément plus +1 ** puis renvoyez le tableau. De plus, si $ c \ _i = 1 $, 1 doit être renvoyé.
③ Lorsque $ c \ _i = 0 $ Je veux insérer le plus petit élément avec -1 et le renvoyer, mais ** le plus petit élément est 1, donc en ajoutant +1 au tout et en insérant 1 **, la relation de grandeur ne change pas. Vous pouvez l'insérer.
④ À d'autres moments Vous devez l'insérer au milieu. Comme mentionné dans la discussion, l'élément doit être plus grand que l'élément $ c \ _i $ th et plus petit que l'élément $ c \ _i + 1 $ th (). Par conséquent, si ($ c \ _i $ ème élément) +1 <($ c \ _i + 1 $ ème élément), alors $ a \ _i = $ ($ c \ _i $ ème élément) +1. C'est bon. Dans d'autres cas, en ajoutant +2 aux éléments après $ c \ _i + 1 $ puis en ajoutant l'original ($ c \ _i + 1 $ e élément) +1 à ** $ a \ _j $ Vous pouvez insérer $ a \ _i $ sans rompre la relation de grandeur de **.
En répétant le retour du ret mis à jour ci-dessus, vous pouvez obtenir $ a \ _i $ qui est le tout fusionné dans la fonction appelante, et vous pouvez le sortir.
(✳︎)… $ c \ _i + 1 $ peut être égal, mais il vaut mieux en faire ** les éléments qui sont inclus dans le même sous-arbre et qui ont une relation de grandeur définie ne sont pas égaux ** Ne marchez pas sur le boîtier.
Quant au montant du calcul, la fonction dfs est appelée jusqu'à $ n $ fois, et chaque montant du calcul est $ O (n) $, donc le montant total est $ O (n ^ 2) $, ce qui est une marge suffisante.
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
vector<vector<ll>> tree;
vector<ll> cost;
bool check;
//Renvoie sous forme de paire index / valeur(Valeur, index)
//Rendez tout différent!(Le traitement lors du port est gênant)
//Du milieu+Pour que la relation ne se brise pas!
vector<pair<ll,ll>> dfs(ll v){
vector<pair<ll,ll>> ret={};
FORA(i,tree[v]){
FORA(j,dfs(i)){
ret.PB(j);
}
}
sort(ALL(ret));
//cout<<cost[v]<<SIZE(ret)<<endl;
if(cost[v]>SIZE(ret)){
check=true;
return {};
}else if(cost[v]==SIZE(ret)){
if(SIZE(ret)==0){
ret.PB(MP(1,v));
return ret;
}else{
ret.PB(MP(ret[SIZE(ret)-1].F+1,v));
return ret;
}
}else if(cost[v]==0){
FOR(i,cost[v],SIZE(ret)-1){
ret[i].F++;
}
ret.PB(MP(1,v));
return ret;
}else{
ll x=ret[cost[v]].F;
if(ret[cost[v]-1].F+1<ret[cost[v]].F){
ret.PB(MP(x-1,v));
return ret;
}else{
FOR(i,cost[v],SIZE(ret)-1){
ret[i].F++;
ret[i].F++;
}
ret.PB(MP(x+1,v));
return ret;
}
}
}
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
check=false;
ll n;cin>>n;
tree=vector<vector<ll>>(n);
cost=vector<ll>(n);
ll root;
REP(i,n){
ll p,c;cin>>p>>c;p--;
if(p!=-1){
tree[p].PB(i);
}else{
root=i;
}
cost[i]=c;
}
vector<pair<ll,ll>> d=dfs(root);
vector<ll> ans(n);
FORA(i,d){
ans[i.S]=i.F;
}
if(check){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
REP(i,n){
if(i!=n-1)cout<<ans[i]<<" ";
else cout<<ans[i]<<endl;
}
}
Après le problème E
Je vais sauter cette fois. Je n'ai pas pu avoir assez de temps pour réfléchir car mon ordinateur ne fonctionnait pas bien.
Recommended Posts