[PYTHON] AtCoder Débutant Contest 155 Critique
Les résultats de cette fois
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