[PYTHON] AtCoder Beginner Contest 179 Bewertung

Die Ergebnisse dieser Zeit

スクリーンショット 2020-09-20 12.14.47.png

Eindrücke dieser Zeit

Dieses Mal war auch ein enttäuschendes Ergebnis. Ich hatte keine Zeit, das F-Problem zu lösen, weil ich das D-Problem die ganze Zeit abgehört hatte. Wenn das F-Problem BIT (oder Seg-Baum) hat, ist es nicht so schwierig, also denke ich, dass ich es in ungefähr 15 Minuten gelöst habe.

Problem A

Ich schrieb die Urteilsbedingungen in umgekehrter Reihenfolge und verbrachte einige Zeit damit.

A.py


s=input()
if s[-1]!="s":
    print(s+"s")
else:
    print(s+"es")

B-Problem

Sie müssen nur gehorsam beurteilen, ob sie gleich sind oder nicht. Seien Sie nur bei Verweisen außerhalb der Reihenfolge vorsichtig.

B.py


n=int(input())
x,y=[],[]
for i in range(n):
    x_,y_=map(int,input().split())
    x.append(x_)
    y.append(y_)
for i in range(n-2):
    if x[i]==y[i] and x[i+1]==y[i+1] and x[i+2]==y[i+2]:
        print("Yes")
        break
else:
    print("No")

C-Problem

$ A \ mal B + C = N $, aber wenn Sie $ A, B $ entscheiden, während Sie $ A \ mal B <N $ erfüllen, wird ** $ C $ eindeutig bestimmt **. Hier wird als $ 1 \ leqq A \ leqq N-1 $ die Zahl ** für $ B $ berechnet, die ** $ A $ entspricht, aber wenn $ N % A = 0 $, $ A \ $ B $, das mal B <N $ erfüllt, ist $ B = 1,2,…, [\ frac {N} {A}] - 1 $ $ [\ frac {N} {A}] - 1 $ Wenn also $ N % A \ neq 0 $, $ A \ mal B <N $ erfüllt ist, ist $ B $ $ B = 1,2,…, [\ frac {N} {A}] $ $ [\ frac {N} {A}] $ wird die Straße sein. Daher durchsucht es alle und gibt die Summe aus.

C.py


n=int(input())
ans=0
for a in range(1,n):
    if n%a==0:
        ans+=(n//a-1)
    else:
        ans+=(n//a)
print(ans)

D Problem

Ich habe das Gefühl, dass ich BIT zum ersten Mal im Produktionswettbewerb von AtCoder verwendet habe. Da dieses BIT Abschnitte hinzufügen kann und ich es nicht implementiert habe, habe ich mir [kamis BIT] ausgeliehen (https://algo-logic.info/binary-indexed-tree/#toc_id_3). Hat. Ich habe Modint darauf gesetzt, ich wusste nicht, wie ich es verwenden soll, und es war 1-indiziert, also habe ich es für immer fehlerhaft gemacht. ** Es ist ziemlich gefährlich, eine Bibliothek zu benutzen, die Sie noch nie benutzt haben ** ...

Da es sich um die Anzahl der Bewegungsmethoden handelt, betrachten Sie zunächst den DP **, der Bewegung als Übergang betrachtet ($ dp [i]: = $ (Anzahl der Bewegungsmethoden in der Masse $ i $). )). Diesmal gibt es jedoch ** $ k $ Abschnitte **. Wenn Sie also jeden Übergang einzeln verarbeiten, ist dies $ O (N ^ 2) $ und nicht rechtzeitig. Da $ k $ maximal 10 ist, sollten Sie hier ** den Übergang für jedes Intervall gut behandeln **. Wenn zu diesem Zeitpunkt das Intervall $ [l, r] $ ist und in der Masse $ i $ liegt, dann ist $ dp [i + l] + = dp [i], dp [i + l + 1] + = dp [i] ],…, Dp [i + r] + = dp [i] $. Daher sollte ** die Abschnittsaddition effizient durchgeführt werden, und die Abschnittsaddition BIT sollte verwendet werden **.

Daher können Sie $ i $ in aufsteigender Reihenfolge betrachten und in der Reihenfolge zu jedem der $ k $ -Abschnitte hinzufügen. Der Berechnungsbetrag beträgt $ O (Nk \ log {N}) $. Da wir den Rest von 998244353 finden möchten, müssen wir mod int in BIT anstelle von long long oder int einfügen.

Darüber hinaus scheint es eine Methode zum Lösen mit $ O (NK) $ nach der imos-Methode, eine Methode zum Reduzieren auf eine formale Klassennummer und eine Methode zum Lösen mit $ O (N \ log {N}) $ unter Verwendung einer formalen Klassennummer ( → maspys Artikel) Aber ich bin mir nicht sicher, also werde ich diesmal überspringen.

D.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 Endungen)、のどちら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.
//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 998244353 //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

/* BIT:RAQ-kompatibles BIT
Der Anfangswert ist a_1 = a_2 = ... = a_n = 0
· Hinzufügen(l,r,x): [l,r)Addiere x zu
· Summe(i): a_1 + a_2 + ... + a_Berechne i
Alle Berechnungen sind O.(logn)
*/
template <typename T>
struct BIT {
    int n;             //Elementanzahl
    vector<T> bit[2];  //Datenspeicherort
    BIT(int n_) { init(n_); }
    void init(int n_) {
        n = n_ + 1;
        for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
    }

    void add_sub(int p, int i, T x) {
        for (int idx = i; idx < n; idx += (idx & -idx)) {
            bit[p][idx] += x;
        }
    }
    void add(int l, int r, T x) {  // [l,r)Hinzufügen
        add_sub(0, l, -x * (l - 1));
        add_sub(0, r, x * (r - 1));
        add_sub(1, l, x);
        add_sub(1, r, -x);
    }

    T sum_sub(int p, int i) {
        T s(0);
        for (int idx = i; idx > 0; idx -= (idx & -idx)) {
            s += bit[p][idx];
        }
        return s;
    }
    T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i ; }
};

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;
}


signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,k;cin>>n>>k;
    BIT<mint> dp(n);
    vector<pair<ll,ll>> sec(k);
    REP(i,k){
        ll l,r;cin>>l>>r;
        sec[i]=MP(l,r);
    }
    dp.add(1,2,1);
    REP(i,n){
        //cout<<i+1<<endl;
        REP(j,k){
            if(i+sec[j].F<=n){
                dp.add(i+sec[j].F+1,min(i+sec[j].S+2,n+1),dp.sum(i+1)-dp.sum(i));
                //cout<<i+1+sec[j].F<<" "<<min(i+1+sec[j].S+1,n+2)<<endl;
            }
        }
    }
    //cout<<1<<endl;
    cout<<dp.sum(n)-dp.sum(n-1)<<endl;
}

E Problem

Ich habe das Gefühl, dass es neulich ein Problem mit der Abwärtskompatibilität gab.

$ A_ {i + 1} = A_ {i} ^ 2 \ mod \ m $ und $ A \ 1 = x $ und finde $ \ sum {i = 1} ^ nA_i $. Zu diesem Zeitpunkt beträgt $ n $ maximal $ 10 ^ 9 $, sodass Sie nicht alle Straßen finden können.

Da jeder Term der Rest von $ m $ ist, gibt es hier höchstens $ m $ Straßen **, und wenn $ (A \ _i = A \ _j) \ mod \ m $ gilt, $ (A ) Da _ {i + 1} = A \ _ {j + 1}) \ mod \ m $ gilt, erscheint eine Schleife mit einer maximalen Länge von $ m $ in der ** Sequenz $ A $.

Wenn Sie diese Schleife finden, können Sie die Berechnung daher mit hoher Geschwindigkeit durchführen, indem Sie berücksichtigen, wie oft die Schleife von ** $ A \ _1 $ bis $ A \ _n $ ** angezeigt wird. Wenn Sie wissen, wie man eine Schleife findet, können Sie sie mit hoher Geschwindigkeit implementieren. Im Folgenden werde ich Ihnen zeigen, wie Sie eine Schleife finden.

① ** Finde $ A \ _i $, wo der Rest zweimal erscheint **

v… Ein Array, das in der Reihenfolge gespeichert wird, in der der Rest angezeigt wird s… eingestellt, um den Rest zu speichern, der herauskam

Schauen Sie sich $ A \ _1, A \ _2,… $ in dieser Reihenfolge an und speichern Sie sie in v und s. Wenn zu diesem Zeitpunkt $ A \ _i $ mit demselben Wert wie in s angezeigt wird, beenden Sie ① mit diesem gespeicherten Wert.

② ** Trennen Sie die Schleife und die Vorderseite der Schleife **

Der in ① gespeicherte Wert ist nicht in der Schleife vor $ A \ _i $ enthalten, die zum ersten Mal angezeigt wird. Daher wird es in diesen Teil (vor der Schleife) und den Teil nach $ A \ _i $ (Schleife) unterteilt.

Wenn sich $ A \ _n $ vor der Schleife befindet, endet die Operation an diesem Punkt und die Ausgabe wird ausgeführt. Wenn $ A \ _n $ in der Schleife enthalten ist, berechnen Sie vor der Schleife, aktualisieren Sie $ n $ auf die verbleibende Anzahl von Begriffen und aktualisieren Sie v, um nur eine Schleife zu sein, nachdem Sie drei Dinge getan haben Fahren Sie mit ③ fort.

③ ** Berechne die Schleife **

Nach ② können Sie folgende Informationen anfordern. l… Schleifenlänge n… Die Länge der verbleibenden Sequenz $ [\ frac {n} {l}] … Wie oft die Schleife erscheint `n% l`… Wie viel dreht sich die Schleife nicht? `s`… Summe in der Schleife ( O (l) $) t… Die Summe der Teile, die nicht um die Schleife laufen

Berechnen Sie die in (2) getrennte Schleife. Die obigen Informationen sind leicht zu finden, daher lautet die Antwort $ [\ frac {n} {l}] \ times s + t $.

E.py


n,x,m=map(int,input().split())
cand=[x]
cands=set()
cands.add(x)
for i in range(m):
    c=(cand[-1]**2)%m
    if c in cands:
        break
    else:
        cand.append(c)
        cands.add(c)
#Der Beginn der Schleife
#print(cand)
p=cand.index(c)
if x<p:
    print(sum(cand[:x]))
    exit()
ans=sum(cand[:p])
cand=cand[p:]
#print(ans)
n-=p
#Anzahl der Schleifen
tim=n//len(cand)
ama=n%len(cand)
ans+=tim*sum(cand)
ans+=sum(cand[:ama])
print(ans)
#print(p)
#print(cand)

F Problem

Es kann durch Verwendung der Intervalladdition BIT nach C gelöst werden. Im Folgenden habe ich versucht, so viel wie möglich in Worten zu erklären, aber es gibt einige Teile, die ich nicht vermitteln konnte. Ich denke, Sie werden Ihr Verständnis vertiefen, indem Sie ** ein Diagramm zeichnen und experimentieren **.

Als ich es zum ersten Mal sah, habe ich es falsch verstanden und die Informationen übersehen ** am nächsten **. Wenn wir das Problem anhand eines Diagramms betrachten, sieht es wie folgt aus.

IMG_0637.PNG

Unter der Annahme, dass die Operationen in der Reihenfolge der eingekreisten Zahlen ausgeführt werden, kann der durch den Pfeil angegebene Teil weiß gestrichen werden. Zu diesem Zeitpunkt ist unter Berücksichtigung von (1) beispielsweise die Anzahl der Zellen, die gezeichnet werden können, wenn jede Linie ausgewählt wird, gering. Wenn Sie auf ② achten, können Sie auch die Anzahl der Quadrate reduzieren, die gezeichnet werden können, wenn jede Spalte ausgewählt wird. In Bezug auf (4) kann auch jede schwarze Zelle in dieser Spalte weiß gemacht werden, da es nicht möglich ist, die Anzahl der Zellen um (2) zu verringern. Mit anderen Worten, wenn Sie eine Zeile (oder Spalte) auswählen, sehen Sie, dass es Operationen gibt, die die Anzahl der Zellen ändern, die die Farbe einer Spalte (oder Zeile) ändern können, und Operationen, die sich nicht ändern **.

Nach weiteren Experimenten speichere ich nun die Spalte ganz links ($ r ) und die bisher ausgewählte obere Zeile ( d $) ** und aktualisiere sie. Wenn Sie dies tun, können Sie sich dies als eine Operation zum Ändern der Anzahl der Zellen ** vorstellen (der Anfangswert ist $ r = c = n $). Wenn Sie beispielsweise $ c $ auswählen, das $ c <r $ erfüllt, und die Operation ausführen, beträgt die Anzahl der Zellen, deren Farbe geändert werden kann, ursprünglich $ r, wenn Sie die 2. bis $ d $ -1. Zeile auswählen. Was -2 $ war, wird auf $ c-2 $ reduziert. Daher werden zusätzlich zu $ r und d $ auch $ row und column $ ** vorbereitet, die den Index der weißen Zelle mit dem kleinsten Index speichern, wenn die Zeile ** $ i $ row und $ i $ ausgewählt werden. Ich werde. Darüber hinaus müssen diese Elemente aktualisiert werden, sodass sie als BIT bezeichnet werden. Natürlich ist auch eine Datenstruktur wie SegmentTreeBeats akzeptabel, mit der der Abschnitt von ** min aktualisiert werden kann, aber ** die Anzahl der Zellen, deren Farbe geändert werden kann, ist vor und nach der Änderung des ausgewählten Abschnitts (✳︎) gleich ** Daher kann es durch Abschnittsaddition verarbeitet werden.

(✳︎)… Wenn Sie in der Abbildung denken, wenn Sie $ (d, 1) $ in ① ausgewählt haben, wird jedes Element von $ row $ von $ n $ durch $ d $ ersetzt. Das heißt, fügen Sie einfach $ d-n $ zu einem beliebigen Element hinzu. Gleiches gilt für jede Operation.

F.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 Endungen)、のどちら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.
//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

/* BIT:RAQ-kompatibles BIT
Der Anfangswert ist a_1 = a_2 = ... = a_n = 0
· Hinzufügen(l,r,x): [l,r)Addiere x zu
· Summe(i): a_1 + a_2 + ... + a_Berechne i
Alle Berechnungen sind O.(logn)
*/
template <typename T>
struct BIT {
    int n;             //Elementanzahl
    vector<T> bit[2];  //Datenspeicherort
    BIT(int n_) { init(n_); }
    void init(int n_) {
        n = n_ + 1;
        for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
    }

    void add_sub(int p, int i, T x) {
        for (int idx = i; idx < n; idx += (idx & -idx)) {
            bit[p][idx] += x;
        }
    }
    void add(int l, int r, T x) {  // [l,r)Hinzufügen
        add_sub(0, l, -x * (l - 1));
        add_sub(0, r, x * (r - 1));
        add_sub(1, l, x);
        add_sub(1, r, -x);
    }

    T sum_sub(int p, int i) {
        T s(0);
        for (int idx = i; idx > 0; idx -= (idx & -idx)) {
            s += bit[p][idx];
        }
        return s;
    }
    T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i ; }
};


signed main(){
    //Code zur Beschleunigung der Eingabe
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,q;cin>>n>>q;
    BIT<ll> row(n);
    row.add(1,n+1,n);
    BIT<ll> column(n);
    column.add(1,n+1,n);
    ll d,r;d=n;r=n;
    ll ans=0;
    REP(_,q){
        ll x,y;cin>>x>>y;
        if(x==1){
            ans+=column.sum(y)-column.sum(y-1)-2;
            //cout<<column.sum(y)-column.sum(y-1)-1<<endl;
            if(y<r){
                row.add(1,d,(y-row.sum(1)));
                r=y;
            }
        }else{
            ans+=row.sum(y)-row.sum(y-1)-2;
            //cout<<row.sum(y)-row.sum(y-1)-1<<endl;
            if(y<d){
                column.add(1,r,(y-column.sum(1)));
                d=y;
            }
        }
    }
    cout<<(n-2)*(n-2)-ans<<endl;
}

Recommended Posts

AtCoder Anfängerwettbewerb 166 Bewertung
AtCoder Anfängerwettbewerb 167 Bewertung
AtCoder Beginner Contest 164 Bewertung
AtCoder Beginner Contest 169 Bewertung
AtCoder Beginner Contest 181 Bewertung
AtCoder Beginner Contest 171 Bewertung
AtCoder Beginner Contest 182 Bewertung
AtCoder Beginner Contest 180 Bewertung
AtCoder Anfängerwettbewerb 177 Rückblick
AtCoder Anfängerwettbewerb 168 Bewertung
AtCoder Beginner Contest 179 Bewertung
AtCoder Beginner Contest 172 Bewertung
AtCoder Anfängerwettbewerb 176 Bewertung
AtCoder Anfängerwettbewerb 175 Bewertung
AtCoder Anfängerwettbewerb 174 Bewertung
AtCoder Beginner Contest 153 Bewertung
AtCoder Anfängerwettbewerb 156 Bewertung
AtCoder Beginner Contest 161 Bewertung
AtCoder Beginner Contest 170 Bewertung
AtCoder Beginner Contest 165 Bewertung
AtCoder Beginner Contest 173 Bewertung
AtCoder Anfängerwettbewerb 155 Bewertung
AtCoder Beginner Contest 162 Bewertung
AtCoder Anfängerwettbewerb 179
AtCoder Anfängerwettbewerb 180
AtCoder Anfängerwettbewerb 173
Atcoder Anfänger Wettbewerb 153
AtCoder Beginner Contest 066 Überprüfen Sie frühere Fragen
AtCoder Anfängerwettbewerb 181 Hinweis
AtCoder Grand Contest 041 Bewertung
AtCoder Regular Contest 105 Bewertung
AtCoder Anfängerwettbewerb 182 Hinweis
AtCoder Grand Contest 048 Bewertung
AtCoder Anfängerwettbewerb 156 WriteUp
AtCoder Grand Contest 045 Bewertung
AtCoder Grand Contest 044 Bewertung
AtCoder Beginner Contest 167 Memorandum
AtCoder Anfängerwettbewerb 183 Hinweis
AtCoder Regular Contest 106 Bewertung
AtCoder Anfängerwettbewerb 184 Hinweis
AtCoder Grand Contest 046 Bewertung
AtCoder Regular Contest 104 Bewertung
AtCoder Beginner Contest 102 Rückblick auf frühere Fragen
AtCoder Beginner Contest 072 Rückblick auf frühere Fragen
AtCoder Beginner Contest 085 Rückblick auf frühere Fragen
AtCoder Beginner Contest 113 Rückblick auf frühere Fragen
AtCoder Beginner Contest 074 Rückblick auf frühere Fragen
AtCoder Beginner Contest 051 Rückblick auf frühere Fragen
AtCoder Beginner Contest 127 Rückblick auf frühere Fragen
AtCoder Beginner Contest 119 Rückblick auf frühere Fragen
AtCoder Beginner Contest 151 Rückblick auf frühere Fragen
AtCoder Beginner Contest 075 Rückblick auf frühere Fragen
AtCoder Beginner Contest 054 Rückblick auf frühere Fragen
AtCoder Beginner Contest 110 Rückblick auf frühere Fragen
AtCoder Beginner Contest 117 Rückblick auf frühere Fragen
AtCoder Beginner Contest 070 Rückblick auf frühere Fragen
AtCoder Beginner Contest 105 Rückblick auf frühere Fragen
AtCoder Beginner Contest 112 Rückblick auf frühere Fragen