[PYTHON] Tokio Marine & Nichido Programmierwettbewerb 2020 Rückblick

Die Ergebnisse dieser Zeit

Die Leistung war um 1270.

Eindrücke dieser Zeit

Das ABC am nächsten Tag war zu schlecht und ich habe alles genommen, aber ich dachte, ich könnte auch diesmal ein bisschen mehr kämpfen. Infolgedessen konnte ich jedoch die Probleme von Yellow Diff und Orange Diff im Test lösen, daher finde ich es gut. Ein hoher Schwierigkeitsgrad kann erreicht werden, wenn Sie sich die Zeit ruhig nehmen (ca. 3 Stunden). Daher möchte ich mich bemühen, diese Geschwindigkeit schrittweise zu erhöhen. Die Leistung ist nicht gut, aber es war eine Zeit, in der ich das Gefühl hatte, kämpfen zu können. Diese Zeiten sind in letzter Zeit vergangen, damit ich die Lösung während des Wettbewerbs beenden kann

Problem A

Gibt drei Zeichen von vorne aus.

A.py

s=input()
print(s[:3])

B-Problem

Ich habe dieses Problem immer wieder behoben und die Leistung ist um etwa 200 gesunken. Es ist zu verschwenderisch. Betrachten Sie die relative Geschwindigkeit zwischen A jagen und B weglaufen. Ich hasse mich deswegen. Ich möchte meinen normalen Geist auch während des Wettbewerbs behalten.

B.py

a,v=map(int,input().split())
b,w=map(int,input().split())
t=int(input())
if a<b and v<=w:
    print("NO")
elif a>b and v<=w:
    print("NO")
elif a<b:
    if -((a-b)//(v-w))<=t:
        print("YES")
    else:
        print("NO")
else:
    if -((-a+b)//(v-w))<=t:
        print("YES")
    else:
        print("NO")

C-Problem

Ich habe versucht, einen verzögerten Segmentbaum (den ich nie implementiert habe) zu verwenden, nur weil ich ihn als Abschnittsaktualisierung angesehen habe. ** Das Problem kann nicht durch Datenstrukturen und Algorithmen gelöst werden **. Es ist überhaupt nicht gut.

Wie Sie anhand der Problemstellung sehen können, erweitert jede Operation ** den Abschnitt, den die Glühbirne beleuchten kann **. Die Lichtintensität einer Glühbirne ist auch die Anzahl der Glühbirnen, die die Glühbirne während des Betriebs beleuchten. Angesichts der Lampenstärke $ B_1, B_2,…, B_N $ für jede Operation beleuchtet die $ i $ -te Lampe die $ i-B_i $ bis $ i + B_i $ -te Lampe. Mit anderen Worten, wenn Sie die Überprüfung der Glühbirnen, die jede Glühbirne beleuchtet, wiederholen (bereiten Sie ein Array der Länge N mit $ 0 $ als Anfangswert vor und stellen Sie alle Glühbirnen im beleuchteten Bereich $ + 1 $ her), einmal Die Operation kann mit $ O (N ^ 2) $ ausgeführt werden. Außerdem ist es ineffizient, allen beleuchteten Abschnitten $ + 1 $ hinzuzufügen, und die imos-Methode kann verwendet werden, um den Rechenaufwand auf $ O (N) $ ** zu reduzieren.

Auf den ersten Blick scheint der Berechnungsbetrag $ O (NK) $ zu sein, aber als ich experimentierte, bemerkte ich, dass er in ungefähr $ \ log {N} $ -Zeiten anstelle von $ K $ -Zeiten abgeschlossen werden kann. Als Bild war der entscheidende Faktor, dass sich ** die minimale Lichtintensität verdoppelte **, wie in der folgenden Abbildung gezeigt. ** Auch wenn Sie sich über Ihre Gedanken nicht sicher sind, können Sie leicht überprüfen, ob es TLE ist, wenn Sie den Maximalfall machen und ihn überprüfen **.

Da es sich um $ O (N \ log {N}) $ handelt, können Sie innerhalb der vorgegebenen Zeit ein Programm schreiben.

C.py

from itertools import accumulate
n,k=map(int,input().split())
a=list(map(int,input().split()))
for _ in range(k):
    b=[0]*n
    for i in range(n):
        b[max(0,i-a[i])]+=1
        if i+a[i]+1<n:
            b[i+a[i]+1]-=1
    a=list(accumulate(b))
    if a==[n]*n:
        break
print(" ".join(map(str,a)))

D Problem

Zunächst besteht kein Zweifel an dem Problem, dass es besser wäre, eine Richtlinie zu formulieren, die auf dem ** Rucksackproblem mit einer begrenzten Anzahl ** basiert.

Unter dieser Voraussetzung können Elemente aus den Vorfahren eines bestimmten Scheitelpunkts und denen im Scheitelpunkt selbst ausgewählt werden. Wenn Sie also Elemente in der Reihenfolge vom Stamm bis zum Scheitelpunkt des Kindes auswählen (** von oben nach unten **), ist dies normal. Man kann es sich wie ein Rucksackproblem vorstellen. In diesem Fall ** kann die Berechnung in der Abfrage vermieden werden **, so dass es bei der Vorberechnung durch DP $ O (NW_ {max}) $ und bei der Berechnung der Abfrage $ O (Q) $ ist, aber $ NW_ { Da max} $ bis zu $ 2 ^ {18} \ times 10 ^ 5 $ betragen kann, kann diese Richtlinie die Berechnung nicht rechtzeitig durchführen. (1)

Wenn Sie jedoch berücksichtigen, dass die Berechnung in der Abfrage durchgeführt wird, ist es ausreichend, die Elemente in der Reihenfolge vom angegebenen Scheitelpunkt zum übergeordneten Scheitelpunkt (** bottom-up **) auszuwählen. Betrachten Sie daher ein Rucksackproblem, das dem vorherigen ähnlich ist. Zum Beispiel ist es $ O (Q W_ {max}) $ bei der Berechnung der Abfrage durch DP. $ Q W_ {max} $ kann jedoch bis zu $ 10 ^ 5 \ mal 10 ^ 5 $ betragen, sodass selbst diese Richtlinie die Berechnung nicht rechtzeitig durchführen kann. (2)

Da jedoch sowohl (1) als auch (2) ungefähr $ 10 ^ {10} $ betragen, wird davon ausgegangen, dass die Grundrichtlinie nicht falsch ist, und ** die Vorberechnung gut durchführen und die Abfrageberechnung effizient durchführen **. Überlegen.

Erstens wird in der Berechnung vor (1), wenn DP an allen $ N $ -Scheitelpunkten ausgeführt wird, dies nicht rechtzeitig sein. Nehmen wir also an, dass DP an $ K $ -Scheitelpunkten ausgeführt wird. Zu diesem Zeitpunkt beträgt der berechnete DP-Betrag $ O (KW_ {max} \ log {N}) $ und $ W_ {max} $ maximal $ 10 ^ 5 $, sodass $ K $ maximal $ 10 ^ 3 $ beträgt. In diesem Fall kann die Vorberechnung innerhalb der Frist durchgeführt werden.

Hier werden in der Abfrageberechnung Elemente in der Reihenfolge vom angegebenen Scheitelpunkt zum übergeordneten Scheitelpunkt ausgewählt, sodass Sie sehen können, dass das Element mit dem Scheitelpunkt näher an der Wurzel mit größerer Wahrscheinlichkeit wiederholt ausgewählt wird . Wenn Sie daher ** $ K $ Scheitelpunkte aus den Scheitelpunkten nahe der Wurzel auswählen, kann die Abfrage schneller berechnet werden ** ( Gemeinsame Teile können durch Vorausberechnung effizienter gestaltet werden !! * *). Da es sich um $ K \ simeq2 ^ {10} -1 $ handelt, kann davon ausgegangen werden, dass die Vorberechnung durch DP bis zum Peak mit einer Tiefe von $ 9 $ abgeschlossen wurde. Da die maximale Tiefe der Scheitelpunkte $ 17 $ von $ N <2 ^ {18} $ beträgt, können wir außerdem sehen, dass wir nur für Elemente mit einer maximalen Tiefe von $ 8 $ von $ 10 $ bis $ 17 $ berechnen müssen. ..

Erwägen Sie daher, den Wert zu maximieren, wenn Sie aus den Elementen oben in $ L $ mit $ L = 8 $ auswählen. Wenn hier DP verwendet wird, ist die Abfrageverarbeitung $ O (QLW_ {max}) $ und nicht rechtzeitig, aber ** Wenn Sie alle aufzählen, ist es $ O (Q2 ^ L) $, also ** $ Q2 ^ L \ simeq10 ^ 7 Ab $ können Sie die Abfrage auch rechtzeitig bearbeiten. (Denken Sie daran, dass die Grundlage des ** Rucksackproblems eine vollständige Aufzählung ** ist !!)

Es scheint auch, dass das Problem, dass ** alles aufzählt, nicht rechtzeitig ist, sondern nur die Hälfte aufzählt und später zusammengefasst wird, als halbe Aufzählung bezeichnet wird **. Als nächstes möchte ich in der Lage sein, ähnliche Probleme zu lösen. Wenn Sie dies wissen, besteht die Idee darin, dass ** die Methode zum Aufzählen aller Elemente in einer Abfrage $ O (QN) $ ist und der Berechnungsaufwand in halber Aufzählung auf $ O (Q \ sqrt {N}) $ reduziert werden kann **. Ich denke ich könnte es schaffen.

Da der Zugriff auf das von DP erstellte Array nach Aufzählung der Hälfte davon in der Abfrage $ O (1) $ sein muss, muss das von DP erstellte Array ** das größte Element mit einer Gewichtung von W oder weniger sein. Es ist auch wichtig zu beachten, dass der Wert ** gespeichert werden muss und der kumulative Maximalwert berechnet werden muss, nachdem der Wert des Maximalartikels mit einem Gewicht W in normalem DP berechnet wurde.

Das obige ist implementiert und wird wie folgt, aber die Implementierung ist schlecht und es kann nicht mit Python und PyPy übergeben werden, aber es kann mit C ++ übergeben werden. Ich hoffe, dass die Implementierung immer besser wird.

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

ll n;vector<pair<ll,ll>> vw;vector<vector<ll>> dp;
ll c1,c2;

void dfs(ll i){
    if(i==1){
        dp[i-1][vw[i-1].S]=vw[i-1].F;
    }else{
        ll j=i/2;
        FORD(k,c2,0){
            if(dp[j-1][k]!=0 or k==0){
                ll ne=k+vw[i-1].S;
                if(ne<=c2)dp[i-1][ne]=max(dp[j-1][k]+vw[i-1].F,dp[i-1][ne]);
            }
            dp[i-1][k]=dp[j-1][k];
        }
    }
    if(i*2<=c1 and i*2<=n)dfs(i*2);
    if(i*2+1<=c1 and i*2+1<=n)dfs(i*2+1);
}

signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    cin>>n;
    vw.resize(n);
    REP(i,n)cin>>vw[i].F>>vw[i].S;
    c1=1<<10;c2=100000;
    dp.resize(c1);REP(i,c1)dp[i].resize(c2+1);
    dfs(1);//cout << 1 << endl;
    REP(i,c1)REP(j,c2)dp[i][j+1]=max(dp[i][j],dp[i][j+1]);
    ll q;cin>>q;
    REP(i,q){
        ll v,l;cin>>v>>l;
        vector<ll> cand;
        while(v>c1){
            cand.PB(v);
            v=v/2;
        }
        ll r=SIZE(cand);//cout << r << endl;
        ll ans=0;
        REP(j,1<<r){
            ll v_sub=0;ll w_sub=0;
            REP(k,r){
                if((j>>k)&1){
                    v_sub+=vw[cand[k]-1].first;
                    w_sub+=vw[cand[k]-1].second;
                }
            }
            if(w_sub<=l)ans=max(ans,dp[v-1][l-w_sub]+v_sub);
        }
        cout<<ans<<endl;
    }
}

D_TLE_py

n=int(input())
vw=[list(map(int,input().split())) for i in range(n)]
#vmax=max(i[0] for i in vw)
#Bereiten Sie DP für die Vorberechnung vor
#1~2^Berechnen Sie zuerst bis zu 10
dp=[[0]*(10**5+1) for i in range(2**10)]
#Vorberechnung
def dfs(i):
    global n,vw,dp
    j=i//2
    for k in range(10**5,-1,-1):
        if dp[j-1][k]!=0 or k==0:
            if k+vw[i-1][1]<=10**5:
                dp[i-1][k+vw[i-1][1]]=max(dp[j-1][k]+vw[i-1][0],dp[i-1][k+vw[i-1][1]])
            dp[i-1][k]=max(dp[j-1][k],dp[i-1][k])
    if i*2<=2**10 and i*2<=n:
        dfs(i*2)
        if i*2+1<=2**10 and i*2+1<=n:
            dfs(i*2+1)
dfs(1)
for i in range(2**10):
    for j in range(10**5):
        dp[i][j+1]=max(dp[i][j],dp[i][j+1])
q=int(input())
for i in range(q):
    #Folgen Sie jedem Teilbaum
    #Entdecken Sie den Rest hier
    v,l=map(int,input().split())
    cand=[]
    while v>2**10:
        cand.append(v//2)
        v=v//2
    r=len(cand)
    ans=0
    for j in range(2**r):
        v_sub=0
        w_sub=0
        for k in range(r):
            v_sub+=vw[cand[k]-1][0]*(j>>k)&1
            w_sub+=vw[cand[k]-1][1]*(j>>k)&1
        if w_sub>l:
            continue
        else:
            ans=max(ans,dp[v-1][l-w_sub]+v_sub)
    print(ans)

E Problem

Das F-Problem wurde noch nicht gelöst (es wird einige Zeit dauern, bis es gelöst ist), daher ist dies das letzte Problem, das in diesem Artikel erklärt wird.

Auf den ersten Blick wusste ich, dass es sich um ein Verpackungsprinzip handelt, aber ich hatte nicht das Gefühl, dass ich es rechtzeitig für meine Implementierung schaffen könnte, sodass ich es nicht lösen konnte. Ich stellte jedoch fest, dass ich es weitergeben könnte, wenn ich es später berechnen würde, und es war dieselbe Methode wie die alternative Lösung der Antwort, daher möchte ich es bis Ende des heutigen Tages überprüfen **.

Im Folgenden ist DP [i] [s, t] = (die Anzahl der Methoden, bei denen das logische Produkt s ist und die logische Summe t ist, wenn i-Nummern ausgewählt werden) **, und die Anzahl der DPs ist begrenzt. Ich habe es implementiert, und wenn ich es richtig implementiert habe, konnte ich es durchsetzen. Es ist keine allgemeine Methode, da ich denke, dass es nicht rechtzeitig für den Berechnungsbetrag sein wird, aber ** Bei DP mit zwei oder mehr Dimensionen kann es durch Verwendung von map beschleunigt werden **, ** In unordeed_map kann das Paar als Schlüssel verwendet werden Ich habe drei Dinge gelernt: Es ist undefiniert ** und ** die Anzahl der DPs ist begrenzt. Wenn Sie sich auf der Rückseite der von DP erstellten Sequenz entscheiden, benötigen Sie kein Array für die temporäre Speicherung und können die Geschwindigkeit beschleunigen **.

E.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

signed main(){
    //Code zur Beschleunigung der Eingabe
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n,k,s,t;cin >> n >> k >> s >> t;
    vector<ll> b(n);REP(i,n)cin >> b[i];
    vector<ll> a;
    REP(i,n){
        bool f=true;
        REP(j,18){
            if((s>>j)&1 and !((b[i]>>j)&1)){
                f=false;break;
            }
            if(!((t>>j)&1) and (b[i]>>j)&1){
                f=false;break;
            }
        }
        if(f)a.PB(b[i]);
    }
    n=SIZE(a);
    k=min(n,k);
    //cout << n << endl;
    //cout << n << endl;
    //unordered_map kann kein Paar als Schlüssel verwenden
    //dp_Es ist langsam, Sub vorzubereiten(Es ändert sich mehrmals, nur indem man sich nicht vorbereitet)
    //OK, wenn Sie es in umgekehrter Reihenfolge tun
    vector<map<pair<ll,ll>,ll>> dp(k);
    REP(i,n){
        FORD(j,k-2,0){
            for(auto l=dp[j].begin();l!=dp[j].end();l++){
                dp[j+1][MP((l->F.F)&a[i],(l->F.S)|a[i])]+=(l->S);
            }
        }
        dp[0][MP(a[i],a[i])]=1;
    }
    ll ans=0;
    REP(i,k)ans+=(dp[i][MP(s,t)]);
    cout << ans << endl;
}

F Problem

Ich bin zufrieden mit der Lösung von E, daher werde ich diesmal darauf verzichten.