AtCoder Débutant Contest 155 Critique

Les résultats de cette fois

スクリーンショット 2020-02-17 19.39.14.png

Impressions de cette époque

(J'ai été trempé dans les skis pendant trois semaines et n'avais aucune motivation pour les professionnels de la compétition, mais j'aimerais reprendre à partir d'aujourd'hui (2/26)) Je n'ai pas pu résoudre jusqu'à C cette fois. Quand j'ai vu la réponse de la solution supposée de D par dichotomie, ce n'était pas difficile en tant qu'idée, alors j'ai senti l'importance de la dévotion. En ce qui concerne E, nous ne pouvions pas faire une bonne distinction selon qu'il faut porter ou non. Je suis très déçu. J'ai l'impression d'avoir dit 200 millions de fois que je voulais penser plus organisé.

Problème A

Sauf le cas où a, b et c sont tous identiques et le cas où a, b et c sont tous différents.

A.py


a,b,c=map(int,input().split())
if (a==b and b==c) or (a!=b and b!=c and c!=a):
    print("No")
else:
    print("Yes")

Problème B

Seulement quand il s'agit d'un nombre pair, vérifiez s'il s'agit d'un multiple de 3 ou d'un multiple de 5, et s'il y a quelque chose qui n'existe pas, cassez-le.

B.py


n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    if a[i]%2==0:
        if a[i]%3==0 or a[i]%5==0:
            continue
        else:
            print("DENIED")
            break
else:
    print("APPROVED")

Problème C

Je veux compter le nombre de chaque chaîne de caractères, donc je la gère dans un dictionnaire. Après avoir compté toutes les chaînes de caractères dans le dictionnaire, si vous listez le dictionnaire, vous aurez une liste avec la "paire clé / valeur" du dictionnaire en un clic. Puisque nous voulons trouver le nombre maximum de chaînes de caractères, nous pouvons trier par le deuxième élément du taple. De plus, lors de la sortie de plusieurs chaînes de caractères, elles sont affichées dans l'ordre alphabétique, donc triez d'abord par le premier élément du taple. Ce qui précède est mis en œuvre et devient comme suit.

C.py


d=dict()
n=int(input())
for i in range(n):
    s=input()
    if s in d:
        d[s]+=1
    else:
        d[s]=1
d=list(d.items())
d.sort(key=lambda x:x[0])
d.sort(key=lambda x:x[1],reverse=True)
m=len(d)
for i in range(m):
    if d[i][1]==d[0][1]:
        print(d[i][0])
    else:
        break

Problème D

Tout d'abord, puisque k vaut 10 ^ 10 au maximum, on peut voir que ** la méthode de vérification de face n'est certainement pas à temps **. Ici, vous pouvez utiliser la ** dichotomie ** car ** la monotonie et la plage de nombres sont fixes **.

En regardant le problème avec la dichotomie à l'esprit, nous trouvons le produit, si positif pour le produit des nombres positifs ou négatifs, négatif pour le produit des nombres positifs et négatifs, au moins un Vous pouvez voir que si est 0, il devient 0. Par conséquent, nous avons examiné chaque cas séparément.

Premièrement, si le kième nombre est négatif, vous pouvez en sélectionner un parmi l'ensemble des nombres positifs (b3) et l'ensemble des nombres négatifs (b1). De plus, ici, le produit du nombre maximum de valeurs absolues est le minimum et -1 est le maximum, donc le kème plus petit nombre dans cet intervalle est recherché par dichotomie. A ce moment, la fonction countk1 est utilisée pour compter le nombre de nombres inférieurs à un certain nombre de t. La fonction countk1 compte le nombre de nombres inférieurs ou égaux au nombre négatif x étant donné un ensemble de nombres positifs et un ensemble de nombres négatifs. Ici, nous allons regarder les éléments de l'ensemble des nombres négatifs dans l'ordre, puis utiliser une dichotomie pour savoir combien de nombres positifs ont un produit de x ou moins ($ O (n )). log n) $).

Ensuite, si le kième nombre devient 0, 0 est calculé tel quel.

Enfin, si le kième nombre est positif, vous pouvez choisir deux nombres parmi un ensemble de nombres positifs ou un ensemble de nombres négatifs, ce qui est un peu plus compliqué. Premièrement, le nombre minimum peut être 1, mais le nombre maximum est le plus grand des produits des deux ensembles avec les valeurs absolues les plus élevées de chaque ensemble, et le nombre d'éléments dans l'un ou l'autre ensemble est de deux. Notez qu'il doit y en avoir plus d'un. Dans ce cas, le k-ième nombre (le cas où il devient négatif et le cas où il devient 0 peut être soustrait à l'avance) peut être recherché par une recherche dichotomique de la même manière que lorsque le k-ième nombre est négatif. Ici, la fonction countk1 Utilisez la fonction countk2 pour le trouver. Comme pour la fonction countk1, vous pouvez en corriger une et effectuer une dichotomie, mais vous devez faire une dichotomie pour chacun des ensembles de nombres négatifs et de l'ensemble positif, dans le même ensemble Il est à noter que pour sélectionner deux nombres sans duplication dans, l'index à rechercher par la dichotomie doit être i + 1 au lieu de 0.

Si vous divisez les cas ci-dessus et écrivez le code de dichotomie avec soin, le code sera le suivant. (C'était difficile à mettre en œuvre ..., j'ai l'impression d'être devenu une personne à part entière quand je peux écrire autant de code rapidement ...)

answerD.cc


#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<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
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#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 INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

ll l1,l2,l3;

ll countk1(ll x,vector<ll> b11,vector<ll> b13){
    ll ret=0;
    REP(i,l1){
        #Partie de recherche de bisection(Satisfait-il x ou moins?)
        ll lx=0;ll rx=l3-1;
        while(lx+1<rx){
            ll t=(lx+rx)/2;
            if(b13[t]*b11[i]<=x){lx=t;}else{rx=t;}
        }
        #Faites attention à la façon d'écrire ici
        if(b13[rx]*b11[i]<=x){
            ret+=(rx+1);
        }else if(b13[lx]*b11[i]<=x){
            ret+=(lx+1);
        }
    }
    return ret;
}

ll countk2(ll x,vector<ll> b21,vector<ll> b23){
    ll ret=0;
    REP(i,l1-1){
        #Le début de la dichotomie est i au lieu de 0+1(Ne pas autoriser la duplication)
        ll lx=i+1;ll rx=l1-1;
        while(lx+1<rx){
            ll t=(lx+rx)/2;
            if(b21[t]*b21[i]<=x){lx=t;}else{rx=t;}
        }
        if(b21[rx]*b21[i]<=x){
            ret+=(rx-i);
        }else if(b21[lx]*b21[i]<=x){
            ret+=(lx-i);
        }
    }
    REP(i,l3-1){
        #Le début de la dichotomie est i au lieu de 0+1(Ne pas autoriser la duplication)
        ll lx=i+1;ll rx=l3-1;
        while(lx+1<rx){
            ll t=(lx+rx)/2;
            if(b23[t]*b23[i]<=x){lx=t;}else{rx=t;}
        }
        if(b23[rx]*b23[i]<=x){
            ret+=(rx-i);
        }else if(b23[lx]*b23[i]<=x){
            ret+=(lx-i);
        }
    }
    return ret;
}

signed main(){
    ll n,k;cin >> n >> k;
    vector<ll> b1,b2,b3;
    REP(i,n){
        ll x;cin >> x;
        if(x<0){b1.PB(x);}else if(x==0){b2.PB(x);}else{b3.PB(x);}
    }
    l1=b1.size();l2=b2.size();l3=b3.size();
    sort(ALL(b1));sort(ALL(b3),greater<ll>());
    if(k<=l1*l3){
        ll l=b1[0]*b3[0];ll r=-1;
        while(l+1<r){
            ll t=(l+r)/2;
            if(countk1(t,b1,b3)>=k){r=t;}else{l=t;}
        }
        if(countk1(l,b1,b3)==k){
            cout << l << endl;
        }else{
            cout << r << endl;
        }
    }else if(k<=l1*l3+l2*(l1+l3)+(l2*(l2-1))/2){
        cout << 0 << endl;
    }else{
        k-=(l1*l3+l2*(l1+l3)+(l2*(l2-1))/2);
        ll l=1;ll r;
        if(l1>=2 and l3<2){
            r=b1[0]*b1[1];
        }else if(l1<2 and l3>=2){
            r=b3[0]*b3[1];
        }else{
            r=max(b1[0]*b1[1],b3[0]*b3[1]);
        }
        sort(ALL(b3));sort(ALL(b1),greater<ll>());

        while(l+1<r){
            ll t=(l+r)/2;
            if(countk2(t,b1,b3)>=k){r=t;}else{l=t;}
        }
        
        if(countk2(l,b1,b3)==k){
            cout << l << endl;
        }else{
            cout << r << endl;
        }
    }
}

E problème

Après quelques expériences, il est facile de voir qu'en raison de l'influence d'autres chiffres ** je ne peux pas me décider avec gourmandise ** (je suis gourmand dès que je quitte le pro de la compétition. Ce n'est pas bon.) Je vais. Les expériences montrent également qu'il existe des moyens de 2 $ pour payer plus ou simplement en faisant attention à un certain chiffre. (C'est facile à comprendre si vous pensez à n = 1 ~ 9.) En d'autres termes, si vous payez 1 de plus pour chaque chiffre (pour payer plus pour le chiffre suivant) et si vous ne payez que ** 2 $ Si vous préparez un tableau pour DP qui contient l'état **, vous pouvez le trouver en décidant dans l'ordre à partir du chiffre supérieur. DP a tendance à bien fonctionner avec cette généralisation, donc j'aimerais faire de mon mieux pour être capable de penser ** sans se précipiter ** pendant le concours.

answerE.py


n=[int(x) for x in list(input())]
k=len(n)
dp=[[-1,-1] for _ in range(k)]
dp[0]=[min(1+(10-n[0]),n[0]),min(1+(10-n[0]-1),n[0]+1)]
for i in range(1,k):
    dp[i]=[min(dp[i-1][1]+(10-n[i]),dp[i-1][0]+n[i]),min(dp[i-1][1]+(10-n[i]-1),dp[i-1][0]+n[i]+1)]
print(dp[k-1][0])

Problème F

Je ne pense pas que ce soit encore adapté au niveau, alors je vais l'ignorer cette fois.

Recommended Posts

Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
Critique du concours AtCoder
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 172
Concours AtCoder Débutant 173
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 181 Remarque
Revue du concours régulier AtCoder 105
Concours AtCoder Débutant 180 Remarque
Concours AtCoder Débutant 182 Remarque
AtCoder Grand Contest 048 Critique
Concours AtCoder pour débutants 156 WriteUp
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Concours AtCoder pour débutants 167
Concours AtCoder Débutant 183 Remarque
AtCoder Regular Contest 106 Évaluation
Concours AtCoder Débutant 184 Remarque
AtCoder Grand Contest 046 Critique
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes