[PYTHON] AtCoder Anfängerwettbewerb 177 Rückblick
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich konnte das D-Problem reibungslos bewältigen, aber obwohl E einfach war, verlor ich meine Konzentration bis zum D-Problem. Es ist ein Spiegelbild. Das F-Problem ist eine Art von Problem, an das ich denken kann, aber ich bin süchtig nach der Methode der Lügenlösung.
Problem A
Überlegen Sie, ob $ t \ times s \ geqq d $ erfüllt werden soll.
A.py
n,x,t=map(int,input().split())
y=-((-n)//x)
print(y*t)
B-Problem
$ len (s) \ times len (t) $ ist ungefähr $ 10 ^ 6 $, also ist es ein Kandidat für eine Unterspalte von $ s $, die mit $ t $ ($ len (s) -len (t) + 1 $ way) übereinstimmt. Alles was Sie tun müssen, ist zu suchen.
B.py
s,t=input(),input()
ls=len(s)
lt=len(t)
ans=1000000000000
for i in range(ls-lt+1):
ans_sub=0
for j in range(lt):
if t[j]!=s[i+j]:
ans_sub+=1
ans=min(ans,ans_sub)
print(ans)
C-Problem
$ \ frac {(A \ _1 + A \ _2 +… + A \ _N) ^ 2- (A \ _1 ^ 2 + A \ _2 ^ 2 +… + A \ _N ^ 2)} {2} $ ist die Lösung Ich werde. Dies ist die Richtlinie, weil ich alle Multiplikationen der beiden Zahlen finden möchte.
Normalerweise scheint es eine kumulative Summenpolitik zu sein, aber ich denke nicht, dass es eine so schwierige Idee ist.
C.py
n=int(input())
a=list(map(int,input().split()))
x=sum(a)
y=sum([(a[i])**2 for i in range(n)])
print(((x**2-y)//2)%(10**9+7))
D Problem
Zuallererst vermute ich ** Union Find **, weil es durch Freundschaft verbunden sein wird. Mit anderen Worten, Freunde sind diejenigen, die in dem Set enthalten sind, das durch eine bestimmte Freundschaft vereint ist.
Teilen Sie nun die $ N $ -Personen in so wenige Gruppen wie möglich auf, damit Sie keine Freunde in der Gruppe haben. Diese Anzahl von Gruppen kann größer oder gleich der maximalen Anzahl von Elementen in jedem Satz des Primärsatzsystems sein, und dies wird ausgegeben.
Mithilfe der Bibliothek von diesem Artikel können Sie auch den Maximalwert des Arrays size ermitteln.
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 Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden 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
//Unten repräsentieren die Primzahl und der Baum dasselbe.
class UnionFind {
public:
vector<ll> parent; //parent[i]Ist der Elternteil von i
vector<ll> siz; //Ein Array, das die Größe der Primzahl darstellt(Initialisieren Sie mit 1)
map<ll,vector<ll>> group;//Assoziatives Array, das für jeden Primsatz verwaltet wird(Schlüssel ist das übergeordnete Element jeder Primzahl, Wert ist ein Array von Elementen dieser Primzahl)
//Konstrukteur
UnionFind(ll n):parent(n),siz(n,1){
//Initialisieren, da die Wurzel aller Elemente selbst ist
for(ll i=0;i<n;i++){parent[i]=i;}
}
//Holen Sie sich die Wurzel des Baums, zu dem Daten x gehören(Führen Sie auch eine Routenkomprimierung durch)
ll root(ll x){
if(parent[x]==x) return x;
return parent[x]=root(parent[x]);//Da der Wert des Zuweisungsausdrucks der Wert der zugewiesenen Variablen ist, kann die Route komprimiert werden.
}
//X- und y-Bäume zusammenführen
void unite(ll x,ll y){
ll rx=root(x);//x root
ll ry=root(y);//Wurzel von y
if(rx==ry) return;//Wenn im selben Baum
//Kleine Menge zu großer Menge zusammenführen(Zusammengeführt von ry zu rx)
if(siz[rx]<siz[ry]) swap(rx,ry);
siz[rx]+=siz[ry];
parent[ry]=rx;//Wenn sich x und y nicht im selben Baum befinden, hängen Sie y root ry an x root rx an
}
//Bestimmen Sie, ob der Baum, zu dem x und y gehören, identisch ist
bool same(ll x,ll y){
ll rx=root(x);
ll ry=root(y);
return rx==ry;
}
//Ermitteln Sie die Größe der Primzahl von x
ll size(ll x){
return siz[root(x)];
}
//Gruppieren Sie jeden Primsatz
void grouping(ll n){
//Führen Sie zuerst die Routenkomprimierung durch
REP(i,n)root(i);
//Mit Karte verwalten(Standard-Build verwenden)
REP(i,n)group[parent[i]].PB(i);
}
};
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n,m;cin>>n>>m;
UnionFind uf(n);
REP(i,m){
ll a,b;cin>>a>>b;
uf.unite(a-1,b-1);
}
uf.grouping(n);
ll ans=0;
FORA(i,uf.group){
ans=max(ans,SIZE(i.S));
}
cout<<ans<<endl;
}
E Problem
Trotz seines Aussehens war es nicht schwierig. Ich möchte die Angewohnheit loswerden, Angst zu haben, indem ich nur hinschaue.
Zunächst müssen wir hier zwei Bedingungen behandeln. Das erste ist, dass $ GCD (A \ _ i, A \ _ j) = 1 $ für jedes $ 1 \ leqq i <j \ leqq N $ gilt. Im zweiten Fall gilt $ GCD (A \ 1, A \ 2,…, A \ N) = 1 $. Die zweite Bedingung ist gut, weil sie nur $ O (N \ log {A {max}}) $ ausführt, aber die erste Bedingung ist $ O (N ^ 2 \ log {A {A { max}}) $.
Ziehen Sie daher in Betracht, die erste Bedingung weiter umzuformulieren. Zuallererst war ** willkürlich ** umständlich zu handhaben, so dass es angesichts der Ablehnung mindestens ein Paar von $ i, j $ gibt, das zu $ GCD (A \ _i, A \ _ j) \ neq 1 $ wird. Ich habe beschlossen, ** zu prüfen, ob es existiert. Zu diesem Zeitpunkt, wenn es zu $ GCD (A \ _i, A \ _j) \ neq 1 $ wird, ist es ausreichend zu zeigen, dass (nicht 1) ** es einen gemeinsamen Bruch gibt **. Daher habe ich beschlossen, die Brüche jedes $ A \ _i $ aufzulisten und zu prüfen, ob dieselben Brüche existieren. Diese Methode ist jedoch schwierig, da der Berechnungsbetrag $ O (N \ sqrt {A \ _ {max}}) $ beträgt (anscheinend funktioniert diese Methode auch in C ++).
Zu diesem Zeitpunkt wurde mir klar, dass nicht alle Brüche aufgelistet werden müssen, sondern nur die in der Primfaktorisierung ** enthaltenen Primzahlen. Mit anderen Worten, wenn $ 12 = 2 \ mal 2 \ mal 3 $ ist, werden $ 2,3 $ aufgezählt (markiert). Zu diesem Zeitpunkt ist es möglich, eine Primfaktorisierung mit $ O (\ log {A_ {i}}) $ durch das Sieb von Eratostenes durchzuführen, und der Gesamtberechnungsbetrag beträgt $ O (N \ log {A_ {i}}) $ Ich werde.
Implementieren Sie von oben aus in der folgenden Reihenfolge.
(1) Array PN_chk, das bei der Primfaktorisierung verwendet wird, Array check, um zu überprüfen, wie oft ein Bruch erscheint, Wörterbuch (oder Satz), um die Zahl zu überprüfen, die in jeder $ A \ _i $ -Primfaktorisierung erscheint Bereiten Sie "prime" vor.
(2) Initialisieren Sie "PN_chk" mit dem Eratostenes-Sieb. Dies ermöglicht eine Primfaktorisierung mit $ O (\ log {A_ {i}}) $.
③ Führen Sie für jedes $ A \ _i $ eine Primfaktor-Zerlegung durch und speichern Sie es in prime. Die gespeicherten Primzahlen werden in "check" aufgezeichnet.
④ Überprüfen Sie, ob 2 oder mehr von jeder Primzahl in check aufgezeichnet sind. Wenn es überhaupt eine gibt, ist es "setwise coprime", wenn der Gesamt-gcd 1 ist, und "not coprime", wenn dies nicht der Fall ist. Wenn keine vorhanden ist, handelt es sich um "paarweise Koprime".
E.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 Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden 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 1000000 //10^6: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
#define PN 1 //Die Primzahl ist 1
//MAXR(=10^6)Angenommen, die ganzen Zahlen bis sind Primzahlen
vector<ll> PN_chk(MAXR+1,PN);//0index entspricht der i-ten ganzen Zahl i(0~MAXR)
//O(MAXR)
void se(){
ll MAXRR=sqrt(MAXR)+1;
//Es zerfällt in Primfaktoren von 2 oder mehr Zahlen, sodass es ignoriert werden kann.
PN_chk[0]=0;PN_chk[1]=0;
FOR(i,2,MAXRR){
//Eine Primzahl, wenn bei Ihrer Ankunft davon ausgegangen wird, dass es sich um eine Primzahl handelt
//Markieren Sie ein Vielfaches einer Primzahl, da diese durch diese Primzahl teilbar ist
if(PN_chk[i]==1) FOR(j,i,ll(MAXR/i)){PN_chk[j*i]=i;}
}
}
vector<ll> check(MAXR+1,0);
//O(logn)
//Beachten Sie, dass die Primzahl in diesem Fall nicht ausgerichtet ist! !! !!
//Einmalige Überprüfung
map<ll,ll> prime;
void prime_factorize(ll n){
if(n<=1) return;
//Wenn 1, ist n eine Primzahl
if(PN_chk[n]==1){prime[n]+=1;return;}
//Markierte Zahlen sind Primzahlen
prime[PN_chk[n]]+=1;
//Betrachten Sie die Anzahl der markierten Zahlen geteilt durch n
prime_factorize(ll(n/PN_chk[n]));
}
signed main(){
se();
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
vector<ll> a(n);REP(i,n)cin>>a[i];
//zweimal überprüfen
REP(i,n){
prime_factorize(a[i]);
FORA(j,prime){
check[j.F]++;
}
prime.clear();
}
ll g=gcd(a[0],a[1]);
FOR(i,2,n-1){
g=gcd(g,a[i]);
}
REP(i,MAXR+1){
if(check[i]>=2){
if(g==1){
cout<<"setwise coprime"<<endl;
}else{
cout<<"not coprime"<<endl;
}
return 0;
}
}
cout<<"pairwise coprime"<<endl;
}
F Problem
Ich konnte es während des Wettbewerbs überhaupt nicht bestehen, aber es schien eine bessere Politik zu sein, als ich erwartet hatte, weil es eine Sendung ** gab, mit der ich die Kandidaten eingrenzen konnte.
Das Folgende ist eine Richtlinie im Einklang mit der Erklärung (ich werde sie zusammenfassen, während ich darüber nachdenke, wie ich darüber nachdenken soll).
Überlegen Sie zunächst, ob Sie sich nach unten oder rechts bewegen möchten. Wenn Sie sich jedoch zur Linie $ k + 1 $ bewegen, beträgt die Anzahl der Bewegungen nach unten immer $ k $. Daher sollte die Mindestanzahl von Zügen berücksichtigt werden ** nur die Mindestanzahl von Zügen nach rechts ** (** Trennung und Vereinfachung von Operationen **).
Wenn Sie sich von einem bestimmten Startpunkt aus bewegen, wird die Anzahl der Bewegungen nach rechts minimiert. Wenn Sie also nach unten gehen können, sollten Sie nach unten gehen (** gierige Bewegung **). Daher kann gesagt werden, dass ** sobald der Startpunkt bestimmt ist, der Endpunkt eindeutig bestimmt ist **. Außerdem müssen Sie nur dann nach rechts gehen, wenn der aktuelle Punkt in $ A \ _i $ bis $ B \ _i $ enthalten ist.
Daher werden wir bei der Verwaltung der Kandidaten (Endpunkt, Startpunkt) in der Reihenfolge von der obersten Zeile aus nachforschen. Aus der obigen Überlegung wird der Endpunkt nur dann nach $ B \ _ {i} + 1 $ verschoben, wenn der Endpunkt in $ B \ _i $ von $ A \ _i $ enthalten ist. Wenn er jedoch nicht enthalten ist, wird der Endpunkt verschoben. Es besteht keine Notwendigkeit, sich zu bewegen. Wenn es beim Verschieben des Endpunkts mehrere Startpunkte gibt (weil wir den Fall finden möchten, in dem die Anzahl der Bewegungen minimal ist), ** sollte nur der maximale Startpunkt übrig bleiben **. Wenn aus $ B \ _ {i} + 1 $ $ W $ wird, müssen die Kandidaten (Endpunkt, Startpunkt) nicht aktualisiert werden.
Um den Fall zu finden, in dem der Endpunkt in $ A \ _i $ bis $ B \ _i $ enthalten ist, speichern Sie die Menge von (Endpunkt, Startpunkt) in set und verwenden Sie lower_bound und superior_bound, um sie zu finden. Das ist gut. Wenn es enthalten ist, wird auch die Anzahl der Elemente reduziert, aber ** die Anzahl der Reduzierungen als Ganzes überschreitet nicht $ W $ **, sodass der Gesamtbetrag der Berechnung $ O ((H + W) \ log {(H +) beträgt. W)}) $.
Um ** die minimale Anzahl von Bewegungen in jeder Linie mit hoher Geschwindigkeit zu finden **, ** speichern Sie den Endpunkt-Startpunkt-Wert ** mit "Multiset" und machen Sie dasselbe wie mit dem vorherigen "Satz". Löschen oder hinzufügen.
Daher wird die Implementierung wie folgt zusammengefasst.
① Bereiten Sie die Kosten für "Set" auf "From" vor, das verwaltet (Endpunkt, Startpunkt), und die Kosten für "Multiset", das die Anzahl der Bewegungen spart (Endpunkt-Startpunkt).
② Initialisieren von und Kosten.
③ Führen Sie Operationen in jeder Zeile aus
(1) Wenn $ [A \ _i, B \ _i] $ einen Endpunkt hat, verschieben Sie den Endpunkt auf $ B \ _i + 1 $ und ändern Sie sowohl von als auch kosten. Möglicherweise ist es auch nicht erforderlich, es zu verschieben. Seien Sie daher bei der Implementierung zu diesem Zeitpunkt vorsichtig. Wenn dann $ B \ _ {i} + 1 $ zu $ W $ wird, fügen Sie nur in Kosten ein, ohne in tofrom einzufügen.
(2) Sehen Sie sich die Kosten nach der Verschiebungsoperation in (1) an. Wenn das kleinste Element nicht INF ist, geben Sie dieses Element aus, und wenn es INF ist, geben Sie -1 aus.
Außerdem ist das Problem, dass Sie nur ein Teil mit "set" oder "multiset" verwalten müssen, indem Sie auf die Auswahlreihenfolge achten, und das Problem, dass Informationen mit mehreren Datenstrukturen verwaltet werden, schwierig. Ich sehe es oft in, also werde ich versuchen, es als Idee zu behalten.
✳️ Ich hatte große Probleme bei der Montage, daher werde ich nachfolgend einige Punkte zusammenfassen.
① ** Ein Paar von Ganzzahlen kann beschleunigt werden **, indem sie in Ganzzahlen konvertiert werden. (2) Wenn Sie das Intervall mit Lower_bound und Upper_bound finden, wird ein Fehler verursacht. Es ist daher besser, von ** Lower_bound zu folgen und zu überprüfen, ob die Bedingung für das obere Ende erfüllt ist **. ③ ** Wenn Sie Erase mit Set oder Multiset verwenden, wird der nächste Iterator zurückgegeben **, sodass die Implementierung sehr einfach ist, wenn Sie bei der Implementierung die while-Anweisung verwenden ③.
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 Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden 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 1000000 //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
signed main(){
//Code zur Beschleunigung der Eingabe
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll h,w;cin>>h>>w;
//Endpunkt,Verwalten Sie den Startpunkt
set<ll> tofrom;
//Verwalten Sie das Minimum
multiset<ll> cost;
REP(i,w){
tofrom.insert(i*MOD+i);
cost.insert(0);
}
REP(i,h){
ll a,b;cin>>a>>b;a--;b--;
auto j=tofrom.lower_bound(a*MOD);
if(j!=tofrom.end()){
ll ne=-1;
while(j!=tofrom.end() or *j<(b+2)*MOD){
cost.erase(cost.lower_bound(ll(*j/MOD)-*j%MOD));
ne=*j%MOD;
j=tofrom.erase(j);
}
if(b==w-1){
cost.insert(INF);
}else{
cost.insert(b+1-ne);
tofrom.insert((b+1)*MOD+ne);
}
}
if(*cost.begin()!=INF)cout<<*cost.begin()+i+1<<"\n";
else cout<<-1<<"\n";
}
}
Recommended Posts