Codeforces Round # 610 (Div.2) Critique Bacha (10/5)
Les résultats de cette fois
Impressions de cette époque
Cette fois, c'était une parade d'erreurs telles que le bug de l'implémentation et une mauvaise lecture. J'aimerais pouvoir le résoudre un peu plus **, mais je suis inquiet car ce n'est pas stable.
Cette semaine, je vais essayer de bacha avec l'intention de ** toujours réduire les bogues d'implémentation et les erreurs de lecture **.
Problème A
Un problème, mais j'ai perdu mon temps parce que ** je n'arrivais pas à bien classer les cas **.
Les observations sont divisées par les positions de $ c-r $ et $ c + r $. De plus, la réponse est la même pour $ a → b $ et $ b → a $, donc échangez $ a $ et $ b $ pour qu'ils soient toujours $ a \ leqq b $.
Je veux connaître les positions de $ c-r $ et $ c + r $, il est donc plus rapide d'expliquer avec des chiffres qu'avec des mots. En d'autres termes, la figure ci-dessous doit être mise en œuvre pour chaque cas.
A.py
for _ in range(int(input())):
a,b,c,r=map(int,input().split())
if a>b:
a,b=b,a
ans=0
if c+r<a:
print(b-a)
elif c+r<=b:
if c-r<=a:
print(b-(c+r))
else:
print(b-(c+r)+(c-r)-a)
else:
if c-r<=a:
print(0)
elif c-r<=b:
print((c-r)-a)
#print(c-r,b)
else:
print(b-a)
Problème B1, problème B2
Je pensais que ce n'était pas si difficile, alors je l'ai résolu ensemble. C'était dangereux parce que c'était envahissant. ** Je regrette d'avoir fait un calcul inutile à un endroit inattendu de la mise en œuvre **. Assurez-vous de le lire avant de le soumettre.
Tout d'abord, il va de soi que vous devriez acheter chez le plus petit. Sur cette base, j'ai pensé à acheter à partir de (seulement) pièces de $ k $ et une avec plus de restrictions, mais si vous expérimentez calmement, vous pouvez d'abord acheter à une personne. Je sais quoi faire. Donc, si vous voulez acheter $ x $ pièces, il est préférable d'acheter ** $ x \% \ k $ pièces d'abord, puis $ xx \% \ k $ pièces par $ k $ pièces ** .. Cependant, lorsque j'essaye tous les $ x $, ce n'est pas à temps pour $ O (n ^ 2) $. Aussi, je pensais que ce serait monotone et pourrait être recherché en deux, mais par exemple, si $ k = 99 $, si $ x = 98 $, vous achèteriez tous les 98 par l'avant. Si $ x = 99 $, vous n'avez qu'à acheter le 99e par l'avant, vous pouvez donc montrer que ** le monotonisme ne tient pas ** (pendant le concours, je n'ai pas remarqué jusqu'à ce que j'ai mis en œuvre la dichotomie. …).
J'ai aussi remarqué que ** faites attention à chaque reste ** en montrant que cette monotonie ne tient pas. En d'autres termes, pour $ x $ dont le reste est $ a $, il est maximisé lorsque $ k $ est pris autant que possible pour ne pas dépasser $ p $. Par conséquent, la valeur maximale pour chaque reste peut être obtenue et la valeur maximale totale doit être sortie.
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
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(i,t){
ll n,p,k;cin>>n>>p>>k;
vector<ll> a(n);REP(i,n)cin>>a[i];
sort(ALL(a));
vector<ll> cand(k,0);
vector<ll> acc(n,0);
acc[0]=a[0];
REP(i,n-1){
acc[i+1]=a[i+1]+acc[i];
}
REP(i,k){
ll q=p;
if(i!=0){
q-=acc[i-1];
}
ll ret=0;
if(q<0)continue;
ret+=i;
REP(j,(n-i)/k){
if(a[i-1+(j+1)*k]<=q){
ret+=k;
q-=a[i-1+(j+1)*k];
}else{
break;
}
}
cand[i]=ret;
}
cout<<*max_element(ALL(cand))<<endl;
}
}
Problème C
Je l'ai mal lu et submergé ...
Dans ce problème, nous trouverons le nombre maximum de problèmes (✳︎) qui peuvent être résolus après que tout problème (problème essentiel) qui satisfait $ t \ _i \ leqq s $ en sortant à $ s $ pendant une certaine période de temps a été résolu. À ce stade, j'ai mal lu la partie (✳︎) et j'ai pensé que c'était le nombre maximum de problèmes requis **, et je suis tombé dans un état où même l'échantillon ne cadrait pas. Comme prévu, ** la politique était parfaite, donc je devrais soupçonner une mauvaise lecture **.
Quoi qu'il en soit, triez les problèmes dans l'ordre de $ t \ _i $ pour le moment. Ici, si vous voulez résoudre les problèmes jusqu'à $ i $ (quand $ t \ i <t \ _ {i + 1} $), vous devez terminer la résolution avant ** $ t \ _ {i + 1} $. **il y a. À ce stade, vous devriez dépenser le plus de temps possible et utiliser jusqu'à $ t \ _ {i + 1} -1 $ pour résoudre. Par conséquent, si vous économisez le temps nécessaire pour résoudre les problèmes 1 à $ i $ sous la forme $ s $, il est nécessaire de satisfaire $ s \ leqq t \ _ {i + 1} -1 $. Tous les problèmes seront résolus **. De plus, ** Étant donné que plusieurs problèmes peuvent devenir des problèmes essentiels à chaque fois, la valeur est enregistrée en tant qu'informations (faciles ou difficiles) du problème à ce moment dans l'ordre croissant au moment où la clé est requise. Vous pouvez le rechercher. Et comme il ne reste plus que $ t {i + 1} -1-s $ après avoir résolu les problèmes requis, il y a ** du temps pour résoudre les problèmes non essentiels restants **. Pendant ce temps, vous devez résoudre autant que possible dans le temps restant dans l'ordre du problème simple → problème difficile parmi les problèmes restants (stocker le nombre de problèmes faciles et difficiles restants dans les variables $ easy, hard $). Mettre.). D'après ce qui précède, le nombre total de problèmes requis et non essentiels est égal au nombre maximum de problèmes qui peuvent être résolus en résolvant les problèmes requis jusqu'au i $ th. Demandez ceci pour tout $ i $ et vous aurez la réponse.
C.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
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll m;cin>>m;
REP(_,m){
ll n,t,a,b;cin>>n>>t>>a>>b;
vector<ll> level(n);REP(i,n)cin>>level[i];
vector<ll> tim(n);REP(i,n)cin>>tim[i];
//Problèmes qui peuvent être résolus en plus(Mec facile,Mec difficile)
ll easy=0;ll hard=0;
//Niveau pour le temps
map<ll,vector<ll>> problem;
REP(i,n){
if(level[i]==0)easy++;
else hard++;
problem[tim[i]].PB(level[i]);
}
//Le plus gros point
ll ans=0;
//Le nombre total de problèmes maintenant
ll now=0;
//Temps requis jusqu'à présent
ll s=0;
FORA(i,problem){
if(s<=i.F-1){
if(s+easy*a>i.F-1){
ans=max(ans,ll(now+(i.F-1-s)/a));
}else{
ans=max(ans,min(ll(now+easy+(i.F-1-s-easy*a)/b),now+easy+hard));
}
}
FORA(j,i.S){
if(j==0){
s+=a;
easy--;
}else{
s+=b;
hard--;
}
now++;
}
}
if(s<=t){
ans=max(ans,now);
}
cout<<ans<<endl;
}
}
Problème après D
Je vais sauter cette fois.
Recommended Posts