[PYTHON] AtCoder Beginner Contest 114 Revue des questions précédentes

Temps requis

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;
}