[PYTHON] AtCoder Beginner Contest 179 Bewertung
Die Ergebnisse dieser Zeit
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}] 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.
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
(✳︎)… 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