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

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Ich hatte die richtige Idee für das E-Problem und das F-Problem, aber ich konnte es nicht AC machen, weil ich die Überlegung und Implementierung nicht abschließen konnte. Da das D-Problem schnell gelöst werden kann, versuche ich, es sorgfältig zu prüfen und umzusetzen. Auch wenn die Implementierung im F-Problem schwierig war, ist die Implementierung nicht so schwierig. Vergessen Sie also nicht ** Überlegungen im Implementierungsteil **.

Problem A

Machen Sie den Fall einfach sorgfältig.

A.py

a,b=map(int,input().split())
if a>=13:
    print(b)
elif a>=6:
    print(b//2)
else:
    print(0)

B-Problem

Notieren Sie sich nacheinander jeden Abschnitt.

B.py

r,d,x=map(int,input().split())
ans=[x]
for i in range(10):
    ans.append(r*ans[-1]-d)
for i in range(1,11):
    print(ans[i])

C-Problem

Nur die i-te ID-Karte, die $ max (L) \ leqq i \ leqq min (R) $ erfüllt, kann mit nur einer Karte alle Tore passieren.

Dies kann wie folgt bewiesen werden. Wenn $ i \ <max (L) $, kann $ L_j = max (L) $ nicht durch das j-te Tor geleitet werden, und wenn $ i > min (R) $, ist $ L_j = max ( R) Kann nicht durch das j-te Tor gehen, das $ ist. Auch wenn $ max (L) \ leqq i \ leqq max (R) $, ist klar, dass die i-te Karte für alle Tore verwendet werden kann. Von oben konnte ich es beweisen.

C.py

n,m=map(int,input().split())
l,r=[],[]
for i in range(m):
    x,y=map(int,input().split())
    l.append(x)
    r.append(y)
ansl,ansr=max(l),min(r)
print(max(0,ansr-ansl+1))

D Problem

Da es möglich geworden ist, sofort auf das grüne Diff zu antworten, möchte ich mich widmen, damit ich sofort aus dem Wasserdiff antworten kann.

Wenn Sie eine Karte auswählen und das Umschreiben wiederholen, wird sie zu O (MN) und ist offensichtlich nicht rechtzeitig. Ziehen Sie daher eine andere Methode in Betracht.

Hier habe ich das Gefühl, dass ich die Anzahl jeder Karte so weit wie möglich erhöhen möchte. Außerdem kann jede Karte neu geschrieben werden, um eine beliebige Anzahl von $ C_1, C_2,…, C_M $ zu erhalten. Wählen Sie also ** die größere $ N $ -Nummer aus allen möglichen Nummern aus ** Ich beschloss, die Politik zu übernehmen.

Wenn Sie ** alle möglichen Zahlen ($ A_1,… A_N, C_1,…, C_M $) als Diktattyp ** speichern, können Sie diese leicht berechnen, indem Sie $ N $ in absteigender Reihenfolge auswählen. tun können.

answerD.py

from collections import Counter
n,m=map(int,input().split())
d=Counter(list(map(int,input().split())))
for i in range(m):
    b,c=map(int,input().split())
    if c in d:
        d[c]+=b
    else:
        d[c]=b
d=sorted(Counter(d).items(),reverse=True)
check=n
ans=0
for i in d:
    if i[1]<check:
        check-=i[1]
        ans+=(i[0]*i[1])
    else:
        ans+=(i[0]*check)
        print(ans)
        break

E Problem

In einem solchen Problem (berechnen Sie die Summe von ** 〇〇, zählen Sie die Anzahl der Muster von 〇〇 usw. **) reicht es nicht aus, alle Muster zu zählen, sodass Sie ** dieselben Muster zusammen zählen können. **. Ich sollte in der Lage sein, es gemäß dieser Richtlinie zu lösen, aber ich konnte es nicht erreichen, egal wie oft ich diese Zählung versucht habe. (← ** Die Ursache ist die Höflichkeit der Rücksichtnahme **. Es ist notwendig, sie richtig zu organisieren, wenn Sie Notizen machen.)

Zuerst,|x_i-x_j|+|y_i-y_j|Wird durch die Quadrate der beiden Teile bestimmtEs gibt zwei QuadrateKDas Muster, das unter den Quadraten der einzelnen Teile ausgewählt wird, sind die Quadrate ohne diese beiden Quadrate.(N \times M-2)VonK-2Denken Sie darüber nach, das Quadrat des Stücks zu wählen,$ _{n \times m-2} C _{k-2}$Es wird auf der Straße sein.

Auch, wie man die beiden Stücke auswählt, auf die man achten soll$ _{n \times m} C _2 Wenn Sie dies auf der Straße belassen, beträgt der BerechnungsbetragO(n \times m)Es wird nicht rechtzeitig sein, also müssen wir mehr Muster zusammenstellen. Was ich hier wissen möchte**|x _i-x _j|+|y _i-y _j|Der Wert des**damit**|x _i-x _j|Wann|y _i-y _j|$の計算は独立にdamitきる**こWannを考慮すれば、それぞれDer Wert desのパターンを別々damit計算しても良いこWannがわかります。

(Nachfolgend der Einfachheit halber|x _i-x _j|Ich denke nur zum Zeitpunkt von|y _i-y _j|Das gleiche gilt zum Zeitpunkt von.)

Deshalb,|x _i -x _j |=kWannkEntspricht dem Wert von(x _i,x _j )Überlegen Sie, wie viele Paare es gibt. Hier,1 \leqq x _i ,x _j \leqq NIst$ x _i,x _j Kann anders sein(\because x _i =x _j $Zum Zeitpunkt von k=Da es 0 ist, wirkt es sich nicht auf die Summe aus)Damit1 \leqq k \leqq N-1Es wird sein. Auch zu diesem Zeitpunkt(x _i,x _j )を組として選ぶDamit$x_j > x _i $Es ist gut so.

Finden Sie daher ein Paar von $ x _i, x _j $, das $ x \ _j-x _i = k (1 \ leqq x _i \ <x _j \ leqq N) $ mit $ 1 \ leqq k \ leqq N-1 $ erfüllt. Sie können sehen, dass es ein $ Nk $ -Paar von $ (x \ _i, x _j) = (1,1 + k), (2,2 + k),… (Nk, N) $ gibt.

Außerdem gibt es für jedes $ x \ _i, x \ _j $ $ y \ _i und y \ _j $ in $ M $, also $ x \ _j-x _i = k (1 \ leqq x _i \ <x) Es gibt $ (Nk) \ mal M ^ 2 $ Kombinationen von $ (x \ _i, y \ _i) $ und $ (x \ _j, y \ _j) $, die _j \ leqq N) $ erfüllen.

Daher keinekFragen Sie danach und addieren Sie,|y _i-y _j|Im Fall von kann die Lösung durch Berechnen und Addieren durch dieselbe Berechnung erhalten werden.

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
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable 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 300000 //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

template<ll mod> class modint{
public:
    ll val=0;
    //Konstrukteur
    modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
    //Konstruktor kopieren
    modint(const modint &r){val=r.val;}
    //Arithmetischer Operator
    modint operator -(){return modint(-val);}//einstellig
    modint operator +(const modint &r){return modint(*this)+=r;}
    modint operator -(const modint &r){return modint(*this)-=r;}
    modint operator *(const modint &r){return modint(*this)*=r;}
    modint operator /(const modint &r){return modint(*this)/=r;}
    //Aufgabenverwalter
    modint &operator +=(const modint &r){
        val+=r.val;
        if(val>=mod)val-=mod;
        return *this;
    }
    modint &operator -=(const modint &r){
        if(val<r.val)val+=mod;
        val-=r.val;
        return *this;
    }
    modint &operator *=(const modint &r){
        val=val*r.val%mod;
        return *this;
    }
    modint &operator /=(const modint &r){
        ll a=r.val,b=mod,u=1,v=0;
        while(b){
            ll t=a/b;
            a-=t*b;swap(a,b);
            u-=t*v;swap(u,v);
        }
        val=val*u%mod;
        if(val<0)val+=mod;
        return *this;
    }
    //Äquivalenzvergleichsoperator
    bool operator ==(const modint& r){return this->val==r.val;}
    bool operator <(const modint& r){return this->val<r.val;}
    bool operator !=(const modint& r){return this->val!=r.val;}
};

using mint = modint<MOD>;

//E / A-Stream
istream &operator >>(istream &is,mint& x){//Fügen Sie x nicht const hinzu
    ll t;is >> t;
    x=t;
    return (is);
}
ostream &operator <<(ostream &os,const mint& x){
    return os<<x.val;
}

//Leistung
mint modpow(const mint &a,ll n){
    if(n==0)return 1;
    mint t=modpow(a,n/2);
    t=t*t;
    if(n&1)t=t*a;
    return t;
}

mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];

//Eine Tabelle erstellen
void COMinit() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    FOR(i,2,MAXR){
        fac[i]=fac[i-1]*mint(i);
        inv[i]=-inv[MOD%i]*mint(MOD/i);
        finv[i]=finv[i-1]*inv[i];
    }
}

//Berechnung des Binomialkoeffizienten
mint COM(ll n,ll k){
    if(n<k)return 0;
    if(n<0 || k<0)return 0;
    return fac[n]*finv[k]*finv[n-k];
}

signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    COMinit();
    ll n,m,k;cin >> n >> m >> k;
    mint ans1=COM(n*m-2,k-2);
    mint ans1_=0;
    FOR(i,1,n-1)ans1_+=(i*m*m*(n-i));
    ans1*=ans1_;
    mint ans2=COM(n*m-2,k-2);
    mint ans2_=0;
    FOR(i,1,m-1)ans2_+=(i*n*n*(m-i));
    ans2*=ans2_;
    cout << ans1+ans2 << endl;
}

F Problem

Zunächst in der Update-Abfrageg(x)=f(x)+|x-a|+bErsetzt mitDa die Berechnung des Absolutwertteils und des Konstantwertteils unabhängig sind, werden sie getrennt berechnet.Ich habs gemacht. Daher ist der Teil b eine einfache Ergänzung, also im FolgendenNur zur Berechnung des AbsolutwertteilsIch werde darauf achten.

des Weiteren,h(x)=|x-x_1|+|x-x_2|+…+|x-x_{n-1}|+|x-x_n|(x_1 \leqq x_2 \leqq … \leqq x_{n-1} \leqq x_n )Wannh(x)Das kleinste x, das minimiert wirdx_{[\frac{n+1}{2}]}Ist eine berühmte Tatsache(Wenn Sie es nachschlagen, wird es herauskommen, und es wird in den vergangenen Fragen von AtCoder herauskommen.), Wenn Sie dies verwendenO(1)Es ist möglich, den Minimalwert von x mit zu finden. Aber es entspricht xf(x)Wenn Sie den Wert von berechnenO(Q)Also denke ich darüber nach, dies mit hoher Geschwindigkeit zu berechnen(In diesem TempoO(Q^2))。

Woran Sie sich hier erinnern sollten, istDa es schwierig ist, den absoluten Wert so zu berechnen, wie er ist, sollten Sie ihn entfernendarüber. Hier ist der MindestwertxNurf(x)Sie müssen nur darauf achtenxuntenx_iÜber|x-x_i|=x-x_idamitxMehr alsx_iEs wird sein. Deshalb,Werde der Kleinstexunten要素を保存する配列A_1とWerde der KleinstexEin Array, das größere Elemente speichertA_2Bereiten Sie zwei vorwird gebraucht(Wenn Sie nicht zwei vorbereiten, ist die Implementierung ziemlich mühsamdamitす。実装も工夫！).. Auch dadurchO(1)damitf(x)は計算damitきますが、この計算Über解説を省略するのdamit自分damit確認してみてください。

Auch hier ist es notwendig, $ O (\ log {n}) $ oder $ O (1) $ in das sortierte Array einzufügen, aber im Fall eines normalen Arrays kostet es $ O (n) $. Ich werde. Hier kann Multiset verwendet werden. ** Multiset kann Daten für $ O (\ log {n}) $ hinzufügen, löschen und suchen ** (Die interne Struktur ist roter und schwarzer Baum, ich habe sie dieses Mal zum ersten Mal verwendet).

Außerdem muss das Element von $ A_1 $ immer kleiner oder gleich dem Element von $ A_2 $ sein, und entweder $ len (A_1) = len (A_2) $ oder $ len (A_1) = len (A_2) + 1 $ gilt. , Das letzte Element von $ A_1 $ wird um $ x $ minimiert, wodurch $ f (x) $, $ len (A_1) minimiert werden, um $ f (x) $ um $ O (1) $ zu berechnen ), Len (A_2), Summe (A_1), Summe (A_2) $ sollten vorbereitet werden und diese Variablen sollten durch die Aktualisierungsabfrage aktualisiert werden. es gibt. Die Implementierungsmethode wird im Kommentar aus dem folgenden Code beschrieben. Wenn Sie dies nicht verstehen, lesen Sie dies bitte.

Darüber hinaus gibt es im folgenden Code einen Code zum Löschen des ersten Elements und des letzten Elements von Multiset. Wenn Sie jedoch den Wert des zu löschenden Elements angeben, werden die Elemente mit demselben Wert gleichzeitig gelöscht. ** Geben Sie den zu löschenden Bereich an muss es tun **.

F.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
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable 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

//Multiset Gleicher Typ gelöscht(Wenn es ein normales Löschen ist)
//Sie müssen lediglich den Bereich mit dem Iterator angeben
signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll q;cin >> q;
    multiset<ll> A1,A2;
    ll B=0;
    ll s1,s2;s1=0;s2=0;
    ll l1,l2;l1=0;l2=0;
    REP(i,q){
        ll x,a,b;cin >> x;
        if(x==1){
            cin >> a >> b;
            B+=b;
            if(i==0){
                A1.insert(a);
                l1+=1;
                s1+=a;
            //l1=Zum Zeitpunkt von l2
            //Überprüfen Sie mit l2 und geben Sie l1 ein, ob es die Vorderseite ist
            //Wenn nicht, setzen Sie das Minimum von l2 in l1
            //Geben Sie zuerst A2 und das Minimum in A1 ein
            }else if((l1+l2)%2==0){
                s2+=a;
                A2.insert(a);
                ll j=*A2.begin();
                s1+=j;
                s2-=j;
                A1.insert(j);
                //A2.erase(j);
                A2.erase(A2.begin(),++A2.begin());
                l1+=1;
            //l1+1=Zum Zeitpunkt von l2
            //Überprüfen Sie mit l1 und geben Sie am Ende l2 ein
            //Wenn nicht, setzen Sie das Maximum von l1 in l2
            //Geben Sie zuerst A1 und dann das Maximum in A2 ein
            }else{
                s1+=a;
                A1.insert(a);
                ll j=*(--A1.end());
                s2+=j;
                s1-=j;
                A2.insert(j);
                A1.erase(--A1.end(),A1.end());
                l2+=1;
            }
        }else{
            ll j=*(--A1.end());
            cout << j << " " << -s1+s2+j*(l1-l2)+B << endl;
        }
    }
}