[PYTHON] AtCoder Beginner Contest 114 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Nachdem ich eine Lösung gefunden hatte, versuchte ich, sie zu organisieren, ohne sie zu organisieren. Daher habe ich lange gebraucht, um sie extra zu implementieren, um das D-Problem zu lösen. Ich möchte die ** Implementierung im Auge behalten, nachdem ich mit dem Organisieren fertig bin und den Pfad ** sehe.

Problem A

Gibt JA aus, wenn der Eingang 3, 5 oder 7 ist.

answerA.py

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

B-Problem

Die Zeichenkette S wird in der Reihenfolge von vorne untersucht und der kleinste Absolutwert der Differenz von 753 ausgegeben.

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))

C-Problem

Für solche Probleme ** Zählen mit einer rekursiven Funktion ** und O (die Anzahl von 753 Zahlen). Ich wollte es jedoch anders machen, um die Implementierung rekursiver Funktionen zu überspringen, und überlegte mir daher eine andere Möglichkeit, alle möglichen Zahlen zu zählen und nach Dichotomie zu suchen. Insbesondere lautet die 753-Nummer `[" 3 "," 5 "," 7 "]`, was das direkte Produkt des ** Arrays ** ist (** die Produktfunktion von itertools ist praktisch **, also denken Sie bitte daran. Denken wir daran.) Von den Zahlen, die als Zeichenkette kombiniert werden, ohne die Reihenfolge zu ändern, erscheinen 3, 5 und 7 mindestens einmal, also füge ich alle diese Zahlen in das ans-Array ein. Dann wird das ans-Array in aufsteigender Reihenfolge sortiert und ** die Anzahl der Elemente, die kleiner oder gleich n sind, wird durch Dichotomie ** durchsucht. (Der letzte Teil der Ausgabe ist verschwenderisch, weil ich einen Fehler im Kopf hatte. Wenn ich den Abfall behebe, sieht es wie ein Kommentar aus.) Sie können auch rekursive Funktionen vermeiden, aber Sie können sofort eine Antwort erhalten, indem Sie zählen, ob es n oder weniger ist, wenn Sie nach den ersten 753 Kandidaten ohne Dichotomie suchen. Mir ist aufgefallen. Die verbesserte Version ist der dritte 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)

D Problem

Da in C ++ mehrere Primzahl-bezogene Bibliotheken vorbereitet sind und die Verarbeitung von Primzahlen in Python oft einige Zeit in Anspruch nimmt, habe ich sie in C ++ implementiert (später wurde mir klar, dass dies in Python doch nicht allzu schwierig ist). Es war.). Da ich vor dem Nachdenken in die Implementierung eingetreten bin, war es ** verschwenderisch **, beispielsweise zu versuchen, eine Tabelle mit Primzahlen zu erstellen.

Im Folgenden werden wir die richtige Antwort betrachten. Zuerst haben wir festgestellt, dass als berühmte Tatsache ** eine ganze Zahl von 1 oder mehr mit einer ungeraden Anzahl von Brüchen die Form eines Quadrats hat **. Im Beispielfall wurde 32400 auch als 75 geschrieben. Wenn Sie also die Route 32400 wählen, können Sie sehen, dass es sich um $ 180 $ handelt, was $ 32400 = 2 ^ 4 \ mal 3 ^ 4 \ mal 5 ^ 2 $ ist. Ich fand auch, dass es gab. Hier erinnere ich mich an eine berühmte Tatsache, die in dieser Angelegenheit sehr wichtig ist. ** Wenn eine Zahl als $ \ prod_ {i = 1} ^ {n} p_i ^ {q_i} $ berücksichtigt wird ($ p_i $ ist eine andere Primzahl, $ q_i $ ist eine ganze Zahl größer oder gleich 1), diese Zahl Die Gesamtzahl der Brüche von ist $ \ prod_ {i = 1} ^ {n} (q_i + 1) $ **. Da die Gesamtzahl der Brüche 75 beträgt, ist $ p_i $ (i = 1 ~ n) so zu betrachten, dass ** $ \ prod_ {i = 1} ^ {n} (q_i + 1) = 75 $. Das ist gut **. Wenn Sie nach $ q_i $ suchen, bevor Sie nach solchen $ p_i $ suchen, gibt es möglicherweise vier Sätze von (4,4,2), (14,4), (24,2), (74) ( Zuerst dachte ich nur an (4,4,2) und war ungeduldig.)

↓ Das Folgende scheint kompliziert zu sein, aber wenn Sie es bisher betrachten können, ist es nicht so schwierig. Wenn also N gegeben ist, werden 1 bis N in Primfaktoren zerlegt und die Anzahl jeder in N! Enthaltenen Primzahl wird gezählt [1], wobei die Primzahl 2 oder mehr enthält, die Primzahl 4 oder mehr enthält, 14 Durch Zählen und Aufzeichnen der Primzahlen, die mehr als 24 Teile enthalten, der Primzahlen, die 24 oder mehr Teile enthalten, und der Primzahlen, die 74 oder mehr Teile enthalten, [2], (4,4,2), (14,4), (24) Sie kann als Antwort erhalten werden, indem berechnet wird, wie viele Fälle es jeweils von 2) und (74) gibt [3] und die Summe ausgegeben wird.

✳︎ Prime_factorize ist eine Funktion, die Primfaktoren zerlegt und in einen Vektor einfügt. Der Berechnungsbetrag beträgt $ O (\ sqrt {n}) $ (Es tut mir leid, wenn ich einen Fehler mache. Ich denke, ich werde später einen Artikel in Qiita als Bibliothek veröffentlichen.)

answerD.cc

//Einschließen
#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<iterator>//Betrieb einstellen(Produktset,Summensatz,Differenzsatz etc.)
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge

using namespace std;
typedef long long ll;

//Makro
#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() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach 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;
}