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

Benötigte Zeit

Impressionen

Ich habe es in der Reihenfolge höher als die Hauptlösung im D-Problem gemacht und bin TLE in Python geworden, also habe ich es C ++ gemacht und es beschleunigt. Diese Lösung ist auch eine wichtige Idee, deshalb würde ich sie gerne lernen.

Problem A

Alles was Sie tun müssen, ist die Straße bis zum Ende zu bewegen.

answerA.py

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

B-Problem

Da es 8 Reduzierungen gibt, werden wir sie mithilfe der Funktion der Reduktionsaufzählung in diesem Artikel zählen. Wenn Sie nur wie viele haben, können Sie berechnen, ohne ein Array vorzubereiten.

answerB.py

def make_divisors(n):
    divisors=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            divisors.append(i)
            if i!=n//i:
                divisors.append(n//i)
    return divisors

ans=0
n=int(input())
for i in range(1,n+1):
    ans+=(len(make_divisors(i))==8 and i%2==1)
print(ans)

C-Problem

Da der Betreff 5000 Billionen Mal mit der Zeichenfolge bearbeitet wird, wird jede in der Zeichenfolge enthaltene Zahl $ x (\ neq1) $ nach 5000 Billionen Mal zu $ x ^ {5000000000000000} $, also ** $ Sie können sehen, dass es deutlich länger als K $ ** ist. Wenn das erste Zeichen ein anderes Zeichen als 1 ist, können Sie daher sehen, dass das $ K $ -Zeichen $ x $ ist. Unter der Annahme, dass 1s vom 1. Zeichen zum $ l $ -Zeichen fortlaufend sind, ist das K-te Zeichen 1, wenn es $ l \ geqq K $ ist. Wenn umgekehrt $ l <K $ ist, ist das K-te Zeichen die l + 1. Zeichennummer.

answerC.py

s=input()
k=int(input())
l=0
for i in s:
    if i=="1":
        l+=1
    else:
        break
print("1" if k<=l else s[l])

D Problem

Da die Fragenabfrage wiederholt nach dem Intervall fragt (bis zu $ 10 ^ 5 $ mal), können Sie sehen, dass Sie die Berechnung des Intervalls hier beschleunigen möchten **. Daher werden wir überlegen, wie für jede Abfrage bis zu $ 10 ^ 3 $ berechnet werden.

Wenn hier die Anzahl der Züge, die durch den Abschnitt [$ l, r $] fahren, $ x_ {l, r} $ beträgt, fahren die Züge durch den Abschnitt von Stadt $ p_i $ zu Stadt $ q_i $. Die Anzahl ist $ (x_ {p_i, p_i} + x_ {p_i, p_i + 1} +… + x_ {p_i, q_i}) + (x_ {p_i + 1, p_i + 1} +… + x_ {p_i + 1 , q_i}) +… + (x_ {q_i, q_i}) = \ Sigma_ {k = p_i} ^ {q_i} {(\ Sigma_ {l = k} ^ {q_i} {x_ {k, l}})} Da es $ (✳︎) sein wird, dachte ich, dass $ k $ (** linkes Ende des Abschnitts **) behoben werden sollte.

Wenn daher der Abschnitt, durch den jeder Zug fährt, anfänglich in Form von [$ L_i, R_i $] angegeben wird, bereiten Sie einen zweidimensionalen Array-Zug vor, in dem das linke Ende des Abschnitts durch welche Stadt und das $ L_i $ th geteilt wird Fügen Sie den am weitesten rechts stehenden Wert $ R_i $ in das Array von ein. Nachdem alle Einfügungen abgeschlossen sind, wird jedes Array sortiert. Wenn in jeder Fragenabfrage $ p_i $ und $ q_i $ angegeben werden, wird ** $ p_i $ das Array zum $ q_i $ das Array (bis zu N Wege) ** ** Zählen Sie einfach die Anzahl der Elemente unter $ q_i $ ** (∵ (✳︎)). Sie können zählen, wie viele Elemente es durch eine Dichotomie ($ O (\ log {M}) $) auf jedem ** (sortierten) Array ** gibt. Daher beträgt der Gesamtbetrag der Berechnung $ O (QN-Protokoll {M}) $. (Erster und zweiter Code, AC für C ++, TLE für Python und PyPy)

Wenn der zu erstellende zweidimensionale Array-Zug ** Zug [$ i ] [ j ] ist: die Anzahl der Züge, deren Abschnitt [ i, j ] ** ist, dann [ L_i, R_i ] ], Durch Hinzufügen von +1 zum Trainieren von [ L_i ] [ R_i $] und Berücksichtigen der kumulierten Summe wird bei der Fragenabfrage nicht dichotomisiert, wie viele Elemente sich unter $ q_i $ befinden. Da es mit ** $ O (1) $ ** berechnet werden kann, beträgt der Berechnungsbetrag O ($ QN + N ^ 2 $). (Dritter Code, AC mit PyPy)

Außerdem wird bisect_right im folgenden Code für die Dichotomie verwendet. Weitere Informationen finden Sie in diesem Artikel.

answerD_TLE.py

import bisect
n,m,q=map(int,input().split())
train=[[] for i in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    train[l-1].append(r-1)
for i in range(n):
    train[i].sort()
for i in range(q):
    p,q=map(int,input().split())
    ans=0
    for i in range(p-1,q):
        ans+=bisect.bisect_right(train[i],q-1)
    print(ans)

answerD.cc

//Referenz: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Einschließen(Alphabetischer Reihenfolge,bits/stdc++.Eine Fraktion, die h nicht benutzt)
#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
#define D()
//Konstante
#define INF 1000000000000 //10^12:Extrem großer Wert,∞
#define MOD 10000007 //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

//↑ Ab hier die Vorlage

signed main(){
    ll n,m,q;cin >> n >> m >> q;
    vector<vector<ll>> train(n);
    REP(i,m){
        ll l,r;cin >> l >> r;
        train[l-1].PB(r-1);
    }
    REP(i,n){
        sort(ALL(train[i]));
    }
    REP(i,q){
        ll p,q_;cin >> p >> q_;
        ll ans=0;
        FOR(j,p-1,q_-1){
            ans+=ll(upper_bound(ALL(train[j]),q_-1)-train[j].begin());
        }
        cout << ans << endl;
    }
}

answerD.py

n,m,q=map(int,input().split())
train=[[0]*n for i in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    train[l-1][r-1]+=1
for i in range(n):
    for j in range(n-1):
        train[i][j+1]+=train[i][j]
for i in range(q):
    p,q_=map(int,input().split())
    ans=0
    for j in range(p-1,q_):
        ans+=train[j][q_-1]
    print(ans)