[PYTHON] Wettbewerbsfähiges Tagebuch für berufliche Hingabe vom 15. bis 17. Tag (7/9 bis 7/11)

<! - Wettbewerbsfähige Vorlage für professionelle Hingabe->

Impressionen

Es tut mir leid, dass ich ABC172-F Unfair Nim nicht lösen konnte. Auch der gestrige Wettbewerb in der ABC-Klasse war eine bedauerliche Wendung, daher bin ich enttäuscht. Vor kurzem war ich frustriert von Wettkampfprofis, aber ich möchte auf dieser Basis wachsen.

Tag 15

Gelöste ABC173-F-Intervalle im Baum. Dieser Artikel erklärt.

16. Tag

ABC136-E Max GCD

Zeit genommen

Ungefähr 40 Minuten (20 Minuten falsch verstanden ...)

Erwägung

Ich wollte ABC172-F Unfair Nim lösen, aber ich konnte es endlich verstehen, nachdem ich die Erklärungsverteilung gesehen hatte, und es schien, dass die Implementierung einige Zeit dauern würde. Also denke ich daran, es morgen zu lösen. (Da es schwierig zu implementieren scheint, werde ich es einmal überspringen.)

Es ist ein blauer Unterschied, aber ich bin froh, dass ich ihn bestehen konnte. Ich habe es jedoch falsch gelesen und 20 Minuten lang verwendet, daher möchte ich vorsichtig sein, es in Zukunft nicht mehr zu tun.

Ich denke, es ist ein einfaches Problem, solange Sie eine Idee haben.

Wählen Sie zuerst $ (i, j) $ und addieren Sie +1 zu $ A_i $ und -1 zu $ A_j $, aber ** diese Operation ändert nicht die Summe ** (** invariant **) !) Nein. Wenn der maximale Wert, der nach der Operation geteilt werden kann, $ X $ ist und der Wert der Zahlenspalte zu diesem Zeitpunkt $ C_i = X \ times B_i $ ist, wird die folgende Formel festgelegt. (Übrigens habe ich falsch verstanden, dass $ A_i $ nur +1 hat.)

X \times B_1+X \times B_2+…+X \times B_n=A_1+A_2+…+A_n \leftrightarrow X\times (B_1+B_2+…+B_n)=A_1+A_2+…+A_n

Mit anderen Worten, $ X $ ist ein ** positiver ** Bruchteil von $ A_1 + A_2 +… + A_n $, also höchstens $ \ sqrt {n} $. Außerdem sollte für jedes $ X $ die Mindestanzahl (✳︎), mit der die Zahlenspalte $ A $ bearbeitet und in die Zahlenspalte $ C $ geändert wird, weniger als $ k $ betragen. Um die Anzahl der Male zu minimieren, ist es hier erforderlich, $ X \ mal B_i $ so nahe wie möglich an $ A_i $ zu bringen (1) ** und ** die Gesamtzahl der Male +1 und -1 Muss gleich sein (2) **.

Nach (1), wenn eine Zahl so nahe wie möglich an einem Vielfachen von $ X $ (** $ Ceil (A_i / X) \ mal X $ oder $ Floor (A_i / X) \ mal X $ ** liegt) Es wird als gut angesehen, aber dieses Mal ist (2) nicht erfüllt, wenn das Muster wie folgt ist.

Nehmen Sie daher zunächst an, dass jedes $ A_i $ $ Ceil (\ frac {A_i} {X}) \ mal X $ ist (** Es ist wichtig, es für Ihre Bequemlichkeit anzunehmen und zu transformieren !) .. Zu diesem Zeitpunkt ist aus $ A_i-Ceil (\ frac {A_i} {X}) \ mal X \ geqq 0 $ $ \ sum_ {i = 1} ^ {n} (A_i-Ceil (\ frac {A_i} {X}) ) \ times X) \ geqq 0 $. Da $ \ sum_ {i = 1} ^ {n} (A_i-B_i \ mal X) = 0 $ ist, ist $ \ sum_ {i = 1} ^ {n} (A_i-Ceil (\ frac {A_i} {) X}) \ times X)> Wenn 0 $, $ lid (\ frac {A_i} {X}) in $ A_i $ $ floor (\ frac {A_i} {X}) \ anstelle von \ times X $ Es kann am besten sein, zu Zeiten X $ zu wechseln. Außerdem gilt $ A_i-Ceil (\ frac {A_i} {X}) \ mal X-X = A_i-Etage (\ frac {A_i} {X}) \ mal X $, also ** $ A_i-Ceil ( $ A_i-Ceil () \ frac {A_i} {X}) \ times Wechseln Sie von X $ zu $ -X $ **… (1) zu $ A_i-floor (\ frac {A_i} {X}) \ times X $ Das $ \ sum_ {i = 1} ^ {n} (A_i- (Ceil (\ frac {A_i} {X}) \ \ oder \ \ Etage (\ frac {A_i} {X})) \ mal X) Machen Sie bis = 0 $ und zählen Sie, dass die Anzahl von +1 (die gleiche wie die Anzahl von -1) zu diesem Zeitpunkt (✳︎) ist und (✳︎) das größte $ X unter $ k $ oder weniger ist. Fragen Sie einfach nach $.

(1)… $ A_i-Ceil (\ frac {A_i} {X}) \ times Es ist leicht intuitiv zu zeigen, dass die Operation von $ -X $ von der mit dem größten X $ die beste ist, daher werde ich sie hier nicht zeigen. (** Zeigen Sie einfach, dass die anderen Optionen nicht optimal sind **, was eine wichtige Idee bei Gier ist).

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)
    #Wenn Sie in absteigender Reihenfolge der Reduzierung sortieren möchten
    divisors.sort(reverse=True)
    return divisors
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in make_divisors(sum(a)):
    x=[a[j]-(a[j]//i)*i for j in range(n)]
    x.sort(reverse=True)
    s=sum(x)
    compk=0
    for j in range(n):
        if s==0:
            break
        else:
            s-=i
            x[j]-=i
            compk+=abs(x[j])
    if compk<=k:
        print(i)
        break

Tag 17

ABC137-E Coins Respawn

Zeit genommen

1 Stunde 5 Minuten

Erwägung

Es hat lange gedauert, bis ich die Bibliothek abgehört habe, nachdem ich die Richtlinie erstellt hatte, aber ich denke, ich werde sie nicht noch einmal abhören, weil ich sie sehr gut organisiert habe.

Ich habe darüber nachgedacht, BFS zu verwenden, um zu folgen, aber ** es ist klar, dass sich das Ergebnis abhängig davon ändert, wie viele Seiten Sie passieren **, also ** verwenden Sie $ P $ -Münzen, wenn Sie durch jede Seite gehen. Als ** dachte ich, ich würde $ C_i-P $ Münzen erhalten, wenn ich durch die $ i $ -te Seite gehe. Daher werden wir im Folgenden prüfen, wie viele Münzen Sie maximal erhalten können, wenn Sie vom Scheitelpunkt $ 1 $ zum Scheitelpunkt $ N $ wechseln, vorausgesetzt, Sie erhalten $ C_i-P $ -Münzen auf der $ i $ -ten Seite. ..

Wenn hier das Vorzeichen der auf jeder Seite erhaltenen Münze umgekehrt wird und die Münze als Abstand betrachtet wird, bewegt sich der Abstand der $ i $ -ten Seite von der Spitze $ 1 $ zur Spitze $ N $ bei $ P-C_i $. Sie können sich das kürzeste Routenproblem vorstellen (einzelner Startpunkt). Da $ P-C_i $ negativ sein kann, verwenden wir die Bellmanford-Methode (** Umkehren des Vorzeichens und Betrachten des Minimums anstelle des Maximums ** als typisches Beispiel).

Es kann auch einen negativen geschlossenen Pfad in einem Diagramm geben, bei dem das Gewicht der Seite negativ ist , und in diesem Problem ist der kürzeste Pfad der kürzeste Pfad, wenn es einen negativen geschlossenen Pfad gibt, der den Scheitelpunkt $ N $ ** enthält Es ist nicht geeignet, weil es nicht fixiert ist. Negative geschlossene Pfade werden in das Diagramm aufgenommen, wenn Scheitelpunkte vorhanden sind, deren kürzester Pfad aktualisiert wird, wenn die Bellmanford-Methodenschleife extra gedreht wird. ( Ich werde Ihnen in Kürze einen zusammenfassenden Artikel über die Bellman Ford-Methode geben **. Bitte beziehen Sie sich auch darauf.)

Hier möchte ich die Existenz eines negativen geschlossenen Pfades zeigen, der den Scheitelpunkt $ N $ enthält, aber es gibt eine ** Lügnerlösung **, die dazu neigt, zu fallen ([Artikel von hamayanhamayan](https: //www.hamayanhamayan). .com / entry / 2019/08/14/131 217)). Um diese Lügenlösungsmethode zu vermeiden, verwenden Sie BFS oder DFS, um die Scheitelpunkte zu verfolgen, die von den Scheitelpunkten aus erreicht werden können, an denen der kürzeste Pfad aktualisiert wird, wenn die Bellmanford-Methodenschleife erneut gedreht wird * * (In meinem Code mache ich das in einer Funktion namens bfs).

Die aus dem Obigen erhaltene Lösung ist (1) Wenn es nicht möglich ist, von Scheitelpunkt 1 zu Scheitelpunkt N zu gelangen → Ausgabe -1 (2) Wenn es von Scheitelpunkt 1 zu Scheitelpunkt N reicht und ein negativer geschlossener Pfad einschließlich des Scheitelpunkts $ N $ → -1 ausgegeben wird. (3) Wenn es von Scheitelpunkt 1 zu Scheitelpunkt N reicht und es keinen negativen geschlossenen Pfad einschließlich Scheitelpunkt $ N $ gibt → Geben Sie das größere von minus und 0 der kürzesten Entfernung aus Es wird sein.

Ähnlich

ABC061-D Score Attack Mein Kommentarartikel

//Zur Compileroptimierung
#pragma GCC optimize("O3")
//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
//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
#define Umap unordered_map
#define Uset unordered_set

struct Edge{
    ll to_Node;
    ll cost;
    Edge(ll t,ll c){to_Node=t;cost=c;}
};

vector<ll> mincost;
vector<vector<Edge>> Edges;
vector<bool> ncycle;
deque<ll> bfsrec;

//Negative Sperrstraßenerkennung
void bfs(){
    ll s=SIZE(bfsrec);
    REP(i,s){
        ll now=*bfsrec.begin();
        bfsrec.pop_front();
        REP(i,SIZE(Edges[now])){
            if(ncycle[Edges[now][i].to_Node]==false){
                ncycle[Edges[now][i].to_Node]=true;
                bfsrec.PB(Edges[now][i].to_Node);
            }
        }
    }
    if(s)bfs();
}

bool bellmanford(ll n){
    //(l1-1)(Gewöhnlicher Pagen)+1(Erkennung)
    for(ll i=0;i<n;i++){
        for(ll j=0;j<n;j++){
            if(mincost[j]!=INF){
                ll e=Edges[j].size();
                for(ll k=0;k<e;k++){
                    ll new_mincost=mincost[j]+Edges[j][k].cost;
                    if(mincost[Edges[j][k].to_Node]>new_mincost){
                        mincost[Edges[j][k].to_Node]=new_mincost;
                        if(i==n-1){
                            ncycle[Edges[j][k].to_Node]=true;//Richtig, wenn es einen negativen Abschluss gibt
                            bfsrec.PB(Edges[j][k].to_Node);
                        }
                    }
                }
            }
        }
    }
    bfs();
    if(ncycle[n-1]==true)return true;
    return false;//Falsch, wenn kein negativer Verschluss einschließlich N vorliegt
}


signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m,p;cin>>n>>m>>p;
    mincost.resize(n);mincost[0]=0;
    FOR(i,1,n-1)mincost[i]=INF;
    Edges.resize(n);
    ncycle.resize(n);
    REP(i,n)ncycle[i]=false;
    //Abzüglich der Kosten um p und umgekehrt
    REP(i,m){
        ll a,b,c;cin>>a>>b>>c;
        Edges[a-1].PB(Edge(b-1,p-c));
        //cout<<p-c<<endl;
    }
    //Betrachten Sie das Minimum darunter
    bool check=bellmanford(n);
    if(check or mincost[n-1]==INF){
        cout<<-1<<endl;
    }else{
        cout<<max(-mincost[n-1],ll(0))<<endl;
    }
}