AtCoder Beginner Contest 114 Revue des questions précédentes

Temps requis

スクリーンショット 2020-04-18 9.58.07.png

Impressions

Après avoir trouvé une solution, j'ai essayé de le faire sans l'organiser, il m'a donc fallu beaucoup de temps pour l'implémenter davantage pour résoudre le problème D. Je veux garder à l'esprit ** l'implémentation après avoir terminé l'organisation et voir le chemin **.

Problème A

Sort YES si l'entrée est 3, 5 ou 7.

answerA.py


x=int(input())
print("YES" if x==3 or x==5 or x==7 else "NO")

Problème B

La chaîne de caractères S est examinée dans l'ordre de l'avant et la plus petite valeur absolue de la différence par rapport à 753 est sortie.

answerB.py


s=input()
l=len(s)
ans=[]
for i in range(l-3+1):
    ans.append(abs(int(s[i:i+3])-753))
print(min(ans))

Problème C

Pour de tels problèmes, ** compter à l'aide d'une fonction récursive ** et O (le nombre de 753 nombres). Cependant, j'ai voulu le faire différemment afin de sauter l'implémentation des fonctions récursives, j'ai donc pensé à une manière différente de compter tous les nombres possibles et de les rechercher par dichotomie. Plus précisément, le nombre 753 est ["3", "5", "7"] `` `, qui est le produit direct du ** array ** (** la fonction produit d'itertools est pratique **, alors souvenez-vous-en. Gardons cela à l'esprit.) Parmi les nombres combinés sous forme de chaîne de caractères sans changer l'ordre, 3 et 5 et 7 apparaissent au moins une fois, donc j'ai mis tous ces nombres dans le tableau ans. Ensuite, j'ai trié le tableau ans par ordre croissant et cherché combien d'éléments ** n ou moins par dichotomie **. (La dernière partie de la sortie est inutile car elle avait un bug dans la tête. Si vous corrigez les déchets, cela ressemblera à un commentaire.) Vous pouvez également éviter les fonctions récursives, mais vous pouvez obtenir une réponse immédiatement en comptant si elle est n ou moins lors de la recherche des 753 premiers candidats sans dichotomie. J'ai remarqué. La version améliorée est le troisième code.

answerC.py


from itertools import product
n=int(input())
ans=[]
for i in range(3,10):
    l=list(product(["3","5","7"],repeat=i))
    for j in l:
        if len(set(j))==3:
            ans.append(int("".join(list(j))))

ans.sort()
m=len(ans)
l,r=0,m-1
while l+1<r:
    k=(l+r)//2
    if ans[k]<n:
        l=k
    elif ans[k]>n:
        r=k
    else:
        l,r=k,k
        break

if ans[l]==n:
    print(l+1)
elif ans[r]==n:
    print(r+1)
elif ans[l]>n:
    print(l)
elif ans[r]<n:
    print(r+1)
elif ans[l]<n:
    print(l+1)
'''
if ans[l]>n:
    print(l)
elif ans[r]<=n:
    print(r+1)
else:
    print(l+1)
'''

answerC_better


from itertools import product
n=int(input())
ans=0
for i in range(3,10):
    l=list(product(["3","5","7"],repeat=i))
    for j in l:
        if len(set(j))==3:
            if int("".join(list(j)))<=n:
                ans+=1
print(ans)

Problème D

Comme il existe plusieurs bibliothèques liées aux nombres premiers préparées en C ++ et qu'il faut souvent du temps pour gérer les nombres premiers en Python, je l'ai implémentée en C ++ (j'ai réalisé plus tard que ce n'est pas trop difficile à faire en Python après tout) C'était.). De plus, comme je suis entré dans l'implémentation avant de réfléchir sérieusement, c'était ** du gaspillage ** comme essayer de faire une table de nombres premiers.

Ci-dessous, nous examinerons la bonne réponse. Tout d'abord, nous avons remarqué que, comme un fait célèbre, ** un entier de 1 ou plus qui a un nombre impair de fractions se présente sous la forme d'un carré **. De plus, dans l'exemple de cas, 32400 a été écrit comme 75, donc si vous prenez la route de 32400, vous pouvez voir que c'est 180 $, ce qui équivaut à 32400 $ = 2 ^ 4 \ fois 3 ^ 4 \ fois 5 ^ 2 $. J'ai également constaté qu'il y en avait. Je rappelle ici un fait célèbre qui est très important dans cette affaire. ** Lorsqu'un nombre est factorisé comme $ \ prod_ {i = 1} ^ {n} p_i ^ {q_i} $ ($ p_i $ est un nombre premier différent, $ q_i $ est un entier supérieur ou égal à 1), ce nombre Le nombre total de fractions de est $ \ prod_ {i = 1} ^ {n} (q_i + 1) $ **. Par conséquent, puisque le nombre total de fractions est de 75, considérons $ p_i $ (i = 1 ~ n) tel que ** $ \ prod_ {i = 1} ^ {n} (q_i + 1) = 75 $. C'est bon **. Si vous cherchez $ q_i $ avant de chercher un tel $ p_i $, il peut y avoir quatre ensembles de (4,4,2), (14,4), (24,2), (74) ( Au début, je ne pensais qu'à (4,4,2) et j'étais impatient.)

↓ Ce qui suit semble compliqué, mais si vous pouvez le considérer jusqu'à présent, ce n'est pas si difficile. Par conséquent, lorsque N est donné, 1 à N sont décomposés en facteurs premiers et le nombre de chaque nombre premier compris dans N! Est compté [1], le nombre premier contenant 2 ou plus, le nombre premier contenant 4 ou plus, 14 En comptant et en enregistrant les nombres premiers qui comprennent plus de 24 morceaux, les nombres premiers qui contiennent 24 morceaux ou plus et les nombres premiers qui contiennent 74 morceaux ou plus, [2], (4,4,2), (14,4), (24) Il peut être obtenu comme réponse en calculant le nombre de cas dans chaque cas de, 2) et (74) [3] et en produisant le total.

✳︎ Prime_factorize est une fonction qui décompose les facteurs premiers et les met dans un vecteur, et le montant du calcul est $ O (\ sqrt {n}) $ (je suis désolé si je fais une erreur. Je pense que je publierai un article dans Qiita en tant que bibliothèque plus tard.)

answerD.cc


//Comprendre
#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<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#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 MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second

void Prime_factorize(vector<ll>& v,ll n){
    if(n<=1) return;
    ll l=ll(sqrt(n));
    FOR(i,2,l){
        if(n%i==0){
        Prime_factorize(v,i);Prime_factorize(v,ll(n/i));return;
        }
    }
    v.PB(n);return;
}

signed main(){
    ll n;cin >> n;
    map<ll,ll> m;
    //[1]
    FOR(i,1,n){
        vector<ll> v;Prime_factorize(v,i);
        REP(j,v.size()){
            if(m.find(v[j])==m.end()){
                m.insert(MP(v[j],1));
            }else{
                m[v[j]]++;
            }
        }
    }
    //[2]
    vector<ll> ans(5,0);
    for(auto i=m.begin();i!=m.end();++i){
        if(i->S>=74)ans[0]++;
        if(i->S>=24)ans[1]++;
        if(i->S>=14)ans[2]++;
        if(i->S>=4)ans[3]++;
        if(i->S>=2)ans[4]++;
    }
    //[3]
    ll rans=0;
    rans+=ll((ans[4]-2)*ans[3]*(ans[3]-1)/2);
    rans+=ans[0];
    rans+=(ans[1]*(ans[4]-1));
    rans+=(ans[2]*(ans[3]-1));
    cout << rans << endl;
}

Recommended Posts

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 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 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
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes