Codeforces Round # 610 (Div.2) Critique Bacha (10/5)

Les résultats de cette fois

スクリーンショット 2020-10-05 20.51.32.png

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.

IMG_2980DEAC0F5E-1.jpeg

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

Codeforces Round # 658 (Div.2) Examen Bacha (7/29)
Codeforces Round # 654 (Div.2) Critique Bacha (8/18)
Codeforces Round # 594 (Div.2) Examen Bacha (10/29)
Codeforces Round # 609 (Div.2) Critique Bacha (10/8)
Codeforces Round # 597 (Div.2) Examen Bacha (10/27)
Codeforces Round # 666 (Div.2) Examen Bacha (9/2)
Codeforces Round # 651 (Div.2) Critique Bacha (8/20)
Codeforces Round # 659 (Div.2) Critique Bacha (8/5)
Codeforces Round # 610 (Div.2) Critique Bacha (10/5)
Codeforces Round # 479 (Div.3) Examen Bacha (9/25)
Codeforces Round # 603 (Div.2) Examen Bacha (10/15)
Codeforces Round # 600 (Div.2) Examen Bacha (10/21)
Codeforces Round # 481 (Div.3) Examen Bacha (9/24)
Codeforces Round # 639 (Div.2) Examen Bacha (9/4)
Codeforces Round # 612 (Div.2) Examen Bacha (10/2)
Codeforces Round # 521 (Div.3) Examen Bacha (10/9)
Codeforces Round # 652 (Div.2) Examen Bacha (8/24)
Codeforces Round # 673 (Div.2) Examen Bacha (10/22)
Codeforces Round # 606 (Div.3) Examen Bacha (10/13)
Codeforces Round # 613 (Div.2) Examen Bacha (10/1)
Codeforces Round # 665 (Div.2) Examen Bacha (8/23)
Codeforces Round # 592 (Div.2) Examen Bacha (11/03)
Codeforces Round # 662 (Div.2) Critique Bacha (8/8)
Codeforces Round # 618 (Div.2) Examen Bacha (9/26)
Codeforces Round # 648 (Div.2) Critique Bacha (9/5)
Codeforces Round # 676 (Div.2) Examen Bacha (10/31)
Codeforces Round # 675 (Div.2) Examen Bacha (10/30)
Codeforces Round # 486 (Div.3) Examen Bacha (9/23)
Codeforces Round # 671 (Div.2) Examen Bacha (9/22)
Codeforces Round # 669 (Div.2) Examen Bacha (9/9)
Codeforces Round # 672 (Div.2) Examen Bacha (10/16)
Codeforces Round # 638 (Div.2) Examen Bacha (9/16)
Codeforces Round # 663 (Div.2) Examen Bacha (8/13)
Codeforces Round # 668 (Div.2) Examen Bacha (9/7)
Codeforces Round # 663 (Div.2) Examen Bacha (8/16)
Codeforces Round # 609 (Div.2) Examen Bacha (10/6)
Codeforces Round # 645 (Div.2) Critique Bacha (9/10)
Codeforces Round # 664 (Div.2) Examen Bacha (8/13)
Codeforces Round # 660 (Div.2) Critique Bacha (8/4)
Codeforces Round # 643 (Div.2) Révision
Codeforces Round # 679 (Div.2) Révision (10/25)
Codeforces Round # 657 (Div.2) Révision
Code de l'éducation forces Round 93 Bacha Review (8/17)
Code de l'éducation forces Round 91 Bacha Review (7/28)
Code de l'éducation forces Round 88 Bacha Review (8/4)
Code de l'éducation forces Round 86 Bacha Review (9/17)
Code de l'éducation forces Round 89 Bacha Review (9/8)
Code de l'éducation forces Round 92 Bacha Review (7/30)
Code de l'éducation forces Round 90 Bacha Review (8/19)
Codeforces Round # 609 (Div.2) (jusqu'à B)
Code de l'Éducation Forces Round 87
Codeforces Beta Round # 13
Codeforces Beta Round # 1
Codeforces Beta Round # 2
DP100 Question Bacha Review 1 ~ 10 (8 / 26,27)
Codeforces Round # 626 B.Compte des sous-rectangles