[PYTHON] AtCoder Beginner Contest 169 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

C Problem Du hast es zu fehlerhaft gemacht ... Ich denke nicht, dass es ungefähr 30 Minuten sind, aber ich denke nicht zu viel darüber nach, also sei nicht zu ungeduldig. Ebenfalls,

Problem A

Ich mache nur die Multiplikation, aber ich setze sie ein, weil der Code zum Ersetzen des durch Eingabe empfangenen Leerzeichens durch $ \ times $ und Ausführen interessant war (der zweite Code).

A.py

a,b=map(int,input().split())
print(a*b)

A_shortest.py

print(eval(input().replace(" ","*")))

B-Problem

Unterbrechen Sie, wenn $ 10 ^ {18} $ überschritten wird, um langsame Berechnungen zu vermeiden. Python kann ** Multi-Multiplikator-Ganzzahlen und extrem große ** Zahlen ausführen, aber Sie sollten sich auch darüber im Klaren sein, dass ** große Zahlen langsamer sind **.

B.py

n=int(input())
a=sorted(list(map(int,input().split())))
ans=1
for i in range(n):
    ans*=a[i]
    if ans>10**18:
        print(-1)
        break
else:
    print(ans)

Wenn Sie es in einer Zeile erzwingen, wird es wie folgt aussehen (leider kann das kürzeste nicht genommen werden). Es ist interessant, dass die for-Anweisung in einer Zeile geschrieben werden kann, wenn sie in der Liste enthalten ist. Daher kann es nützlich sein, sich daran zu erinnern, aber sie verringert die Lesbarkeit. Ich denke, es ist besser, sie zu vermeiden.

B_oneline.py

t=1;print([t:=(-1,t:=t*int(a))[0<=t<=1e18]for a in[*open(0)][1].split()][-1])

C-Problem

Problem B verlief reibungslos, aber ich habe viel Zeit mit Problem C verbracht. ** Ich denke, es war eine gute Entscheidung, über 20 Minuten nachzudenken und aufzugeben und mit dem nächsten Problem fortzufahren **.

Ich habe während des Wettbewerbs den folgenden Code geschrieben. Schließlich ist bei diesem Problem die ** Genauigkeit von Dezimalbrüchen ** ein Problem, daher dachte ich, ich sollte sie in eine Ganzzahl konvertieren und berechnen. Aus diesem Grund habe ich den Dezimalpunkt genommen und ihn korrespondieren lassen. (Siehe auch diesen Artikel und Kommentare dazu.)

C.py

a,b=input().split()
a=int(a)
b=int("".join(b.split(".")))
#b=int(b.strip("."))
print((a*b)//100)

Unten finden Sie einen verkürzten Code, der auf diesem Code basiert. Ich persönlich mag die Substitutionsformel, weil sie in Mode ist, also habe ich versucht, sie zu verwenden.

C_shorter.py

print(int((s:=input())[:-4])*int(s[-4]+s[-2:])//100)

Es scheint, dass Sie das Dezimalmodul in Python verwenden können, um den Dezimalbruch dieses Problems genau zu berechnen **.

C_decimal.py

from decimal import Decimal
a=int(a)
b=Decimal(b)
print(int(a*b))

Darüber hinaus kann ** unter Verwendung des Bruchmoduls, das rationale Zahlen ohne Fehler berechnet **, wie im ersten Code unten berechnet werden und wenn Sie nach dem Runden von $ b $ auf eine Ganzzahl berechnen möchten Mit der Rundungsfunktion können Sie vor der Berechnung auf die nächste Ganzzahl runden.

Der obige Inhalt wird unter Bezugnahme auf diesen Artikel ausführlich beschrieben.

C_fractions.py

from math import floor
from fractions import Fraction
a,b=input().split()
a=int(a)
b=Fraction(b)
print(int(a*b))

C_round.py

a,b=input().split()
a=int(a)
b=round(float(b)*100)
print(a*b//100)

D Problem

Da z durch die Potenz einer Primzahl dargestellt wird, führen wir zuerst eine Primfaktorzerlegung durch.

Die Bibliothek für die Primfaktorisierung wird in diesem Artikel vorgestellt, und die Methode des Eratostenes-Siebens reicht hinsichtlich des Berechnungsbetrags nicht aus, sodass die Methode der Versuchsteilung für Primfaktoren verwendet wird. Ich habe es zerlegt.

Wenn in Primfaktoren zerlegt, ist $ n = p_1 ^ {q_1} \ mal p_2 ^ {q_2} \ mal… \ mal p_k ^ {q_k} $ ($ p_1, p_2,… p_k $ ist eine Primzahl $ q_1, q_2,… q_k $ Ist eine ganze Zahl größer oder gleich $ 1 $).

Überlegen Sie nun, wie viele Operationen mit jeder Primzahl ausgeführt werden können. Unter Berücksichtigung der Primzahl $ p_i $, die in der Primfaktorisierung nur in $ q_i $ enthalten ist, sollte die durch die Operation ausgewählte ganze Zahl z in der Reihenfolge von $ p_i ^ 1, p_i ^ 2, ... $ berücksichtigt werden **.

Da die Summe der Schultern der Potenz $ q_i $ ist, kann sie auch als ** $ 1 + 2 +… + x \ leqq q_i $ umformuliert werden, indem das größte x ** ($ 1) gefunden wird. Im Fall von + 2 +… + x \ neq q_i $ sollten alle Unterschiede zu x) addiert werden.

Wenn Sie also ein Array vorbereiten, in dem das ** $ l $ -te Element $ 1 + 2 +… + l $ ** ist, ist der Index des größten Elements unter $ q_i $ in einem solchen Array. Kann als Bitten umschrieben werden. Ein solches Element kann als Element neben Upper_bound umformuliert werden, das für jede Primzahl berechnet und addiert werden kann.

(Ich persönlich denke, es war ein beachtliches Wachstum, dass ich hier auf die Idee der Dichotomie kommen konnte. Ich bin froh, dass das Ergebnis der Hingabe herauskam.)

D.cc

//Einschließen(Alphabetischer Reihenfolge)
#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
//für Schleifenbeziehung
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden um 1 dekrementiert.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x ist ein Container wie ein Vektor
#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)) //Finden Sie den Maximalwert
#define MIN(x) *min_element(ALL(x)) //Finden Sie den Mindestwert
//Konstante
#define INF 1000000000000 //10^12:Extrem großer Wert,∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays(Wird für die Aufzählung von Primzahlen usw. verwendet.)
//Abkürzung
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares

map<ll,ll> prime;//Karte, um zu speichern, wie viele jede Primzahl durch Primfaktorisierung herausgekommen sind

//O(√n)
//Ausgerichtet(Karte wird automatisch nach Schlüssel angeordnet)
void prime_factorize(ll n){
    if(n<=1) return;
    ll l=sqrt(n);
    FOR(i,2,l){
        if(n%i==0){
        prime_factorize(i);prime_factorize(ll(n/i));return;
        }
    }
    //Auch wenn der Schlüssel nicht in der Karte vorhanden ist, wird er automatisch erstellt.
    prime[n]++;return;
}

signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n;cin >> n;
    prime_factorize(n);
    vector<ll> num(100);
    REP(i,100){
        num[i]=i+1;
        if(i>0)num[i]+=num[i-1];
    }
    ll ans=0;
    for(auto i=prime.begin();i!=prime.end();i++){
        //cout << i->F << " " << i->S << endl;
        ans+=(ll(upper_bound(ALL(num),i->S)-num.begin()));
    }
    cout << ans << endl;
}

E Problem

Dieses Mal konnte ich das Problem, das ich beim letzten Mal mit ARC nicht lösen konnte, in wenigen Minuten lösen, ** das beste finden und zeigen, ob es angemessen war **.

Zunächst einmal ist in diesem Problem ** die Definition des Medianwerts abhängig von der Gleichmäßigkeit der Länge der Sequenz unterschiedlich. Betrachten wir also den Fall anhand der Gleichmäßigkeit **.

Wie beiden gemeinsam ist, gilt $ A_i \ leqq X_i \ leqq B_i $, sodass der Medianwert von $ A_1, A_2,…, A_n $ das mögliche Zentrum von $ X_1, X_2,…, X_n $ ist. Der Medianwert von $ B_1, B_2,…, B_n $ ist ** Minimum ** und der Medianwert von $ X_1, X_2,…, X_n $ ist ** Maximum **. Außerdem kann ** $ X_i $ um 1 verschoben werden, sodass Sie sehen können, dass es jeden Medianwert darstellen kann, der zwischen dem Minimal- und dem Maximalwert liegen kann **. (Ich habe ein Experiment durchgeführt, um dies zu zeigen, aber wenn ich alles schreibe, ist es redundant. Weitere Informationen finden Sie unter Hauptlösung.)

Betrachten wir von hier aus die Fallklassifizierung nach gerade und ungerade. Beachten Sie zunächst, dass für gerade Zahlen ** der Median ein Bruchteil ** sein kann. Das heißt, wie Sie aus der ersten Stichprobe sehen können, wenn der minimale Median $ \ frac {3} {2} $ und das Maximum $ \ frac {5} {2} $ ist, dann $ \ frac { Es sind 3} {2}, 2, \ frac {5} {2} $, sodass Sie zählen können, wie viele in Schritten von $ \ frac {1} {2} $ möglich sind. Wenn es ungerade ist, ist der Medianwert nur eine Ganzzahl, sodass Sie zählen können, wie viele in Schritten von $ 1 $ sein können.

Deshalb implementieren wir dies und erhalten:

answerE.py

n=int(input())
a,b=[],[]
for i in range(n):
    c,d=map(int,input().split())
    a.append(c)
    b.append(d)
a.sort()
b.sort()
if n%2==0:
    x=[a[n//2-1],a[n//2]]
    y=[b[n//2-1],b[n//2]]
    print(sum(y)-sum(x)+1)
else:
    x=a[n//2]
    y=b[n//2]
    print(y-x+1)

F Problem

Für solche Probleme reicht es zunächst nicht aus, die Muster aller Mengen aufzulisten und dann zu zählen. Wenn Sie hier darauf achten, ** wie viele Elemente ausgewählt sind **, können Sie herausfinden, wie Sie das Element mit $ O (NX) $ als $ O (X) $ auswählen.

Berücksichtigen Sie daher in diesem Problem, dass ** $ A_1, A_2,…, A_N $ einzeln ausgewählt werden **. Außerdem möchte ich eine Teilmenge betrachten, deren Summe $ S $ ist. Wählen Sie also $ k $ aus der Teilmenge von $ dp [i] [j] [k] = $ ($ A_1, A_2,…, A_i $). (Die Anzahl der Dinge, deren Summe $ j $ ist).

Darunter ist die Ausgabeantwort der Teil, der die Teilmenge $ U $ enthält, die "$ dp [N] [S] [k] \ times $ ($ dp [N] [S] [k] $" ist. Die Anzahl der Kandidaten für die Menge $ T $… ①) ”ist die Summe von $ k $. Außerdem ist ① $ 2 ^ {N-k} $, also ist die Antwort die Summe von $ dp [N] [S] [k] \ mal 2 ^ {N-k} $ für $ k $.

** Diese Lösung ist jedoch $ O (N ^ 2S) $, daher muss der Rechenaufwand reduziert werden **. Wenn man bedenkt, ob es beim Übergang von $ DP $ in der Teilmenge $ U $ enthalten ist, und schließlich die Berechnung des Produkts mit der Anzahl der Kandidaten der Teilmenge $ T $ berücksichtigt, ist es ineffizient, also ** Teilmenge Betrachten Sie den Übergang von $ DP $ bei gleichzeitiger ** Prüfung, ob er in $ U $ und $ T $ enthalten ist. ( Verwenden Sie nur, ob es in der Teilmenge $ U $ im Übergang enthalten ist → Können Sie sich vorstellen, ob es in der Teilmenge $ U $ und der Teilmenge $ T $ im Übergang enthalten ist? Das ist der Punkt ... </ font>)

mod=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0]*(s+1) for i in range(n+1)]
dp[0][0]=1
for i in range(n):
    for j in range(s+1):
        if j-a[i]>=0:
            dp[i+1][j]=dp[i][j]*2+dp[i][j-a[i]]
        else:
            dp[i+1][j]=dp[i][j]*2
        dp[i+1][j]%=mod
print(dp[n][s])