[PYTHON] AtCoder Regular Contest 105 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Nur die A- und B-Probleme konnten gelöst werden, und es stellte sich heraus, dass das B-Problem später eine Lügenlösungsmethode war. Als ich versuchte, das C-Problem zu lösen, wurden nur einige Fälle zu WA und ich hatte große Probleme. Da das C-Problem eine gierige Methode ist, können Fehler existieren, aber es fällt mir immer noch schwer, nicht zu wissen, was falsch ist.

(Es war schwierig, aber ich habe es auf dem längsten Weg gemäß der Lösungsmethode gelöst. Einzelheiten finden Sie in der Erklärung des C-Problems unten.)

Problem A

Überlegen Sie, ob es in zwei Teile passt. Zu diesem Zeitpunkt ist es gut zu denken, dass die Gesamtzahl, die durch eine bestimmte Auswahl ausgewählt wurde, genau die Hälfte der Gesamtzahl betragen sollte.

Wenn also bestimmt wird, ob eines von $ a + b, b + c, c + d, d + a, a + c, b + d, a, b, c, d $ genau halbiert ist. Ist gut. Außerdem müssen Sie bei der Auswahl von drei Zahlen nicht nachdenken.

A.py

a,b,c,d=map(int,input().split())
cand=[a+b,b+c,c+d,d+a,a+c,b+d,a,b,c,d]
s=sum([a,b,c,d])
if s%2==1:
    print("No")
elif s//2 in cand:
    print("Yes")
else:
    print("No")

B-Problem

Mach die Simulation ehrlich. Da nur noch eine Nummer übrig ist und dieselbe Operation für dieselbe Nummer ausgeführt wird, speichern Sie die Nummer mit set. Ausgerichtete Sätze sind praktisch, da Sie die maximale und minimale Anzahl auswählen.

Der Testfall wurde während des Wettbewerbs schwach bestanden, aber diese Lösung ist eine falsche Lösung. Wenn es beispielsweise zu $ 1 \ 10 ^ 9 $ wird, wird es mal in die Menge $ 10 ^ 9 $ eingefügt. Daher ist die richtige Antwort zu erkennen, dass diese Operation eine Methode der gegenseitigen Teilung von Euklidisch ist, und die gesamte gcd zu nehmen. Wenn Sie simulieren (Maximalwert) - $ x \ times $ (Minimalwert) > 0, können Sie auch nur das Maximum $ x $ simulieren. Wenn Sie dies tun, ist es wahrscheinlich schneller. Sollte arbeiten.

B.cc

//Debug-Optionen:-fsanitize=undefined,address

//Compileroptimierung
#pragma GCC optimize("Ofast")

//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//Makro
//für Schleife
//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.
//FORA ist ein Bereich für Aussagen(Wenn es schwer zu bedienen ist, löschen Sie es)
#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--)
#define FORA(i,I) for(const auto& i:I)
//x ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//Konstante
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays
//Abkürzung
#define PB push_back //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;cin>>n;
    set<ll> ans;
    REP(i,n){
        ll a;cin>>a;
        ans.insert(a);
    }
    while(SIZE(ans)!=1){
        ll l,r;l=*ans.begin();r=*--ans.end();
        ans.erase(r);
        ans.insert(r-l);
    }
    cout<<*ans.begin()<<endl;
}

C-Problem

Ich konnte mit der gierigen Methode für das C-Problem keine AC machen, also schrieb ich das Programm, indem ich den längsten Erklärungsweg einbezog. Obwohl es in Bezug auf die Berechnung schwerer ist als die Erklärung, haben wir das Beschneiden hinzugefügt, um es zu beschleunigen.

Versuchen Sie zuerst eine Kamelbestellung und es ist $ N! $. Zusätzlich ist es für jede Bestellung $ O (M \ mal N ^ 2) $, um den Abstand zwischen Kamelen zu ermitteln, der zum Überqueren jedes Teils benötigt wird. Daher beträgt der Berechnungsbetrag $ O (N! \ Times M \ times N ^ 2) $, was zu spät ist. Beschleunigen Sie also, indem Sie gut beschneiden ** (ich habe während des Wettbewerbs aufgegeben). Bis zu ** $ 10 ^ {11} $ können jedoch auch bei einer nicht angenommenen Lösung durch Beschleunigung um einen konstanten Faktor ** vergehen. Geben Sie also nicht auf.)

Erstens ist die oben genannte Richtlinie

① Bestimmen Sie die Reihenfolge der Kamele (verwenden Sie einfach $ next $ \ _ $ permutation $ (Referenz). (2) Beginnen Sie mit einem Kamel mit jedem Teil ($ M $ Straße) und finden Sie heraus, welches Kamel ($ N-1 $ Straße) nicht geladen werden kann.

Es wird in der Reihenfolge sein.

Wenn Sie in ② die ** gierige Methode verwenden, treten Sie auf den Eckfall und werden WA **. Beginnen Sie hier mit einem Kamel und betrachten Sie die Informationen darüber, welches Kamel nicht als ** Seite ** platziert werden kann (muss durch die Länge des Teils getrennt werden), das erste Kamel bis zum letzten Kamel. Es wäre schön, wenn wir das Problem der Suche nach dem längsten Weg reduzieren könnten.

Daher sollte DP mit $ dp [i]: = $ (der längste Abstand vom ersten Kamel zum $ i $ -ten Kamel) in der do-while-Anweisung von $ next $ \ _ $ permutation $ erfolgen. .. Die Zeit, zu der ein bestimmtes Teil ausgewählt wird, wird als Übergang angesehen, Details werden hier jedoch weggelassen.

(Im Folgenden wird die Geschwindigkeit um einen konstanten Faktor erhöht.) (Sicher, Sie können durch einfaches Beschleunigen durchkommen, um den ersten Teil zu reduzieren.)

Wenn $ (a, b), (c, d) $ existiert, werden Teile nach (Länge, Gewicht) verwaltet und zu $ a \ geqq c $ und $ b \ leqq d $, $ (a, b) Wenn $ erfüllt ist, gilt auch $ (c, d) $. ** Sie können die Anzahl der Teile reduzieren, sodass die Größe der Länge und die Größe des Gewichts zwischen beliebigen Teilen übereinstimmen **. Ordnen Sie daher die Teile in aufsteigender Reihenfolge der Länge an, schauen Sie sich das mit der größten Länge und das mit der kleinsten Länge an und prüfen Sie, ob das kleinere nicht verwendet wird, wenn das oben Gesagte zutrifft. Da dies mit jedem Teil erfolgt, beträgt der Gesamtbetrag der Berechnung $ O (M ^ 2) $. Sie können auch ** Teile beschneiden, die einmal überprüft wurden, weil Sie nicht danach suchen müssen.

Als nächstes **, wenn das schwerste Kamel nicht am Rand ist, ist es besser, es am Rand zu platzieren ** (nicht bewiesen), damit Sie das letzte Kamel mit dem schwersten Kamel reparieren können. Sie müssen nur an die Reihenfolge der Kamele auf $ (N-1)! $ Denken.

Außerdem sind die Teile in aufsteigender Reihenfolge des Gewichts angeordnet ($ \ leftrightarrow $ aufsteigende Reihenfolge der Länge). Wenn also ein Teil nicht von einem Kamel platziert werden kann, befindet sich das Kamel, auf dem der nächste Teil nicht platziert werden kann, hinter diesem Kamel. Daher können Sie den Rechenaufwand ** wie bei der Skalierungsmethode ** speichern.

Durch Beschleunigen um die obigen konstanten Zeiten wird $ O (N! \ Zeit M \ mal N ^ 2) $ in $ O (M ^ 2 + (N-1) geändert! Sie können es fallen lassen. In Anbetracht des schlimmsten Falls $ N = 10, M = 100000 $ kann er auf ungefähr $ 10 ^ {11} $ → $ 10 ^ {10} $ fallen gelassen werden. Ich habe auch für $ 10 ^ {10} $ gekürzt, sodass ich es auf 26 ms fallen lassen konnte (am schnellsten ab dem 13. Oktober 2020). Wenn die Geschwindigkeit auf dieses Niveau erhöht werden kann, denke ich, dass es auch im schlimmsten Fall möglich sein wird, durchzukommen.

C_fastest.cc

#pragma GCC optimize("Ofast")

#include<bits/stdc++.h>
using namespace std;

#define REP(i,n) for(int i=0;i<int(n);i++)
#define REPD(i,n) for(int i=n-1;i>=0;i--)
#define SIZE(x) int(x.size())
#define INF 2000000000
#define PB push_back
#define F first 
#define S second

int w[8];
pair<int,int> partsx[100000];
bool info[100000];
int n,m;
vector<pair<int,int>> parts;

inline int read(){
	int x=0,w=0;char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return w?-x:x;
}

signed main(){
    n=read();m=read();
    REP(i,n)w[i]=read();
    sort(w,w+n);
    REP(i,m){partsx[i].F=read();partsx[i].S=read();}
    sort(partsx,partsx+m);
    int ma=INF;
    REP(i,m)ma=min(ma,partsx[i].S);
    if(ma<w[n-1]){
        cout<<-1<<endl;
        return 0;
    }
    REP(i,m)info[i]=true;
    REPD(i,m){
        if(!info[i])continue;
        REP(j,i){
            if(partsx[i].S<=partsx[j].S){
                info[j]=false;
            }
        }
    }
    REP(i,m)if(info[i])parts.PB(partsx[i]);
    m=SIZE(parts);
    int ans=INF;
    do{
        vector<int> dp(n,0);
        REP(j,n-1){
            int k=j;int check=w[k];
            REP(i,m){
                while(k!=n){
                    if(parts[i].S<check){
                        dp[k]=max(dp[j]+parts[i].F,dp[k]);
                        break;
                    }
                    k++;
                    check+=w[k];
                }
                if(k==n){
                    dp[n-1]=max(dp[j],dp[n-1]);
                    break;
                }
            }
        }
        ans=min(ans,dp[n-1]);
    }while(next_permutation(w,w+n-1));
    cout<<ans<<endl;
}

Nach D Problem