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

Benötigte Zeit

Impressionen

Das Problem war schwierig und ich rang ein paar Tage nach Bachacon. Ich brauchte viel Denkvermögen und Wissen über BIT (Binary Indexed Tree), deshalb möchte ich es zusammenfassen. Ich habe BIT in einem anderen Artikel auf leicht verständliche Weise erklärt.

Problem A

Beachten Sie, dass Sie "n-i + 1" ausgeben sollten.

answerA.py

n,i=map(int,input().split())
print(n-i+1)

B-Problem

Ich möchte numpy für diese Art von Gitterproblem verwenden. Ich hoffe, ich kann in naher Zukunft lernen, wie man Numpy bedient. Die Implementierung ist leicht zu verstehen, wenn die Vorgänge ohne die Zeilen und Spalten separat ausgeführt werden.

answerB.py

h,w=map(int,input().split())
a=[]
#Ausgeschlossen sind Linien, die nur aus weißen Quadraten bestehen
for i in range(h):
    k=input()
    if k!="."*w:
        a.append(k)
l=len(a)

ans=[[] for i in range(l)]
#Ausgeschlossen sind Spalten, die nur aus weißen Quadraten bestehen
for i in range(w):
    for j in range(l):
        if a[j][i]=="#":
            for k in range(l):
                ans[k].append(a[k][i])
            break
for i in range(l):
    print("".join(ans[i]))

C-Problem

Es ist am besten, ** k aufeinanderfolgende Kerzen ** anzuzünden, und es gibt n-k + 1 mögliche Kandidaten. Da wir uns am Anfang am Punkt der Koordinate 0 befinden, gibt es für jeden Kandidaten zwei Muster, eines von Koordinate 0 → linkes Ende → rechtes Ende und das andere von Koordinate 0 → rechtes Ende → linkes Ende, also dieses $ 2 \ mal (n) -k + 1) Finde die Mindestzeit (= zurückgelegte Strecke) in der $ Straße.

answerC.py

n,k=map(int,input().split())
x=list(map(int,input().split()))
mi=10**10
for i in range(n-k+1):
    mi=min(mi,x[k-1+i]-x[i]+min(abs(x[i]),abs(x[k-1+i])))
print(mi)

D Problem

Ich habe versucht, den Median gut zu finden, aber ** falsch verstanden **, dass die angegebene Zahlenfolge überhaupt sortiert wurde. Ich habe auch die richtige Antwort gelesen und verstanden, aber ich hatte das Gefühl, dass es ziemlich schwierig und meine Fähigkeiten unzureichend waren. Da es sich jedoch um ein sehr informatives Problem handelte, möchte ich es ausführlich erläutern. Wie im vorherigen Eindruck erwähnt, werde ich BIT als bekannt erläutern. Weitere Informationen zu BIT finden Sie in diesem Artikel. ..

Erstens müssen wir die Medianbedingung ** abstrahieren, um das Auffinden zu erleichtern ** (dieses Gefühl der Abstraktion wird wahrscheinlich zunehmen, wenn wir mehr Probleme lösen).

Unter der Annahme, dass der Medianwert der Zahlenfolge b der Länge M x ist, gibt es Elemente von x oder mehr in ①: b, die $ [\ frac {M} {2}] $ oder mehr sind, und ②: ① ist erfüllt. Es sind zwei Bedingungen erforderlich: x ist das Maximum. … (✳︎)

Was Sie daran sehen können, ist, dass es ** eintönig ** ist. Daher können wir sehen, dass der Medianwert durch die Dichotomie gefunden werden kann (** Median → Dichotomie scheint häufig aufzutreten **).

Da ich festgestellt habe, dass ich es durch Dichotomie finden kann, werde ich "Bedingungen betrachten, bei denen der Medianwert der Subjektnummernfolge $ m $ ** x oder mehr ** ist" ... (1).

Von (✳︎) setzt (1) den Medianwert von $ (a_l, a_ {l + 1},…, a_ {r}) $ auf $ m_ {l, r} (1 \ leqq l \ leqq r \ leqq N) Es gibt $ [\ frac {_ {n + 1} C 2} {2}] $ oder mehr $ m {l, r} $, das x oder mehr ist, wenn es $ ist ... (2) Ich kann es schaffen

Wenn (✳︎) auf die gleiche Weise verwendet wird, hat $ (a_l, a_ {l + 1},…, a_ {r}) $ ein Element von x oder mehr in $, damit $ m_ {l, r} $ x oder mehr ist. Sie können auch sehen, dass [\ frac {r-l + 1} {2}] $ oder mehr ausreicht. … (3)

Daher wird nur die Information ** x oder mehr oder weniger als x benötigt **. Wenn also die erstere 1 ist und die letztere ** ersetzt wird **, ist (3) $ (a_l, a_ {l +). 1},…, a_ {r}) Die kumulative Summe der $ Elemente $ S_ {l, r} $ ist 0 oder mehr… (4).

Wenn hier die kumulative Summe $ S_k $ von $ (a_1, a_2,…, a_ {k}) $ erhalten und zuerst durch die kumulative Summe gespeichert wird, ist $ S_ {l, r} = S_r-S_ {l -1} $ und (4) ist $ S_r-S_ {l-1} \ geqq 0 \ leftrightarrow S_ {l-1} \ leqq Es kann als S_r $… (5) umformuliert werden.

Weiterhin ist (5) $ S_ {l-1} \ leqq Da es S_r (1 \ leqq l \ leqq r \ leqq N) $ ist, ist es der gleiche Wert, selbst wenn er als $ S_l \ leqq S_r (0 \ leqq l <r \ leqq N) $… (6) umformuliert wird.

Aus der obigen Überlegung ergibt sich für (1), dass $ S_l \ leqq S_r $ $ [\ frac {_ {n + 1 + 1 für $ l, r $ ist, das $ 0 \ leqq l <r \ leqq N $ erfüllt. } C _2} {2}] Es kann umformuliert werden, dass es $ oder mehr gibt, und wir werden in Betracht ziehen, danach zu fragen.

Wenn Sie zu diesem Zeitpunkt $ l und r $ berücksichtigen, beträgt der Berechnungsbetrag $ O (n ^ 2) $, jedoch mit ** r fest (r \ *) **, $ S_l \ $ l $, das leqq S_ {r ^ \ *} $ und $ 0 \ leqq l <r ^ \ * $ erfüllt, wird tatsächlich von $ O (\ log {n}) $ mit ** BIT erhalten, also ** $ O (n \ log {n}) $ kann verwendet werden, um das Paar von $ l, r $ zu bestimmen.

Bei Verwendung der vorherigen BIT wird das $ i $ -te Element (1-indiziert) des vom BIT verwalteten Arrays $ B $ auf ** Kumulative Summe $ S_r (0 \ leqq r \ leqq r ^ \ * - gesetzt) 1) Erfüllen Sie $ S_l \ leqq S_ {r ^ \ *} $ und $ 0 \ leqq l <r ^ \ * $, indem Sie festlegen, wie oft $ i $ in $ ** erscheint. $ l $ kann berechnet werden mit $ B_1 + B_2 +… + B_ {S_ {r ^ \ *}} $.

Auch für ** wie oft die kumulative Summe $ S_r (0 \ leqq r \ leqq r ^ \ * -1) $, die zu $ i $ wird, erscheint **, $ B_ {S_ für jedes r Fügen Sie einfach {r}} $ hinzu.

Außerdem kann die kumulative Summe $ S_r (0 \ leqq r \ leqq n) $ kleiner oder gleich 0 sein, sodass $ 1-S_min $ zu allen kumulierten Summen addiert wird, sodass der Mindestwert 1 ist.

Wenn alles oben Genannte implementiert ist, wird es wie folgt sein.

✳︎… Auch nachdem die Implementierungsrichtlinie festgelegt wurde, habe ich einen Fehler im Index gemacht und das Segfo ausgegeben oder einen Fehler in der Ausgabe gemacht, daher möchte ich vorsichtig sein.

answerD.cc

//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
//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


//1-indexed
class BIT {
public:
    ll n; //Datenlänge
    vector<ll> bit; //Datenspeicherort
    BIT(ll n):n(n),bit(n+1,0){} //Konstrukteur

    //bit_x bis i bis o(log(n))Fügen Sie mit hinzu
    void add(ll i,ll x){
        if(i==0) return;
        for(ll k=i;k<=n;k+=(k & -k)){
            bit[k]+=x;
        }
    }

    //bit_1 + bit_2 + … + bit_n-1 + bit_n bis O.(log(n))Fragen Sie nach
    ll sum(ll i){
        ll s=0;
        if(i==0) return s;
        for(ll k=i;k>0;k-=(k & -k)){
            s+=bit[k];
        }
        return s;
    }
};

ll solve(vector<ll>& a,ll x,ll n){
    vector<ll> b(n,-1);
    REP(i,n)if(a[i]>=x)b[i]=1;
    vector<ll> s(n+1,0);
    
    //Hier war es anders ...
    FOR(i,1,n)s[i]=s[i-1]+b[i-1];

    ll base=1-MIN(s);REP(i,n+1)s[i]+=base;
    BIT T(MAX(s));
    ll ret=0;
    REP(i,n+1){
        ret+=T.sum(s[i]);
        T.add(s[i],1);
    }
    return ret;
}

signed main(){
    ll n;cin >> n;
    vector<ll> a(n,0);vector<ll> c(n,0);
    REP(i,n){cin >> a[i];c[i]=a[i];}
    sort(ALL(c));c.erase(unique(ALL(c)),c.end());
    //Finden Sie die Antwort durch Dichotomie
    ll check=((n+1)*n/2)/2;
    ll l,r;l=0;r=SIZE(c)-1;
    while(r>l+1){
        ll h=(l+r)/2;
        if(solve(a,c[h],n)>=check){
            l=h;
        }else{
            r=h;
        }
    }
    #if 0
    //Debug-Code
    REP(i,SIZE(c)){
        cout << c[i] << " " << solve(a,c[i],n) << endl;
    }
    #endif

    //Wieder der Fehler, l und r umzukehren ...
    if(solve(a,c[r],n)>=check){
        cout << c[r] << endl;
    }else{
        cout << c[l] << endl;
    }
}