[PYTHON] Codeforces Round # 643 (Div. 2) Review
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich habe AtCoder vor ungefähr einem Jahr gestartet, aber ich habe mich entschieden, in Kodofo zu erscheinen, der hörte, dass es viele Wettbewerbe gibt. Ich werde es vorerst nicht tun, weil es zu viele Probleme gibt, um die letzten Fragen zu beantworten, aber ich werde jedes Mal herauskommen, wenn die Zeit nicht zu spät ist. Dies ist das zweite Mal, und ich bin nicht an das Kodofo-Format und die Fragensätze auf Englisch gewöhnt, aber ich denke, ich bekomme gute Noten. Darüber hinaus bietet ABC im Grunde eine Erklärung für alle Fragen AC, aber Kodofo wird versuchen, nur die Probleme, die gelöst werden können, und die Probleme, die wahrscheinlich bald gelöst werden, leicht zu erklären.
Problem A
Als ich es zum ersten Mal sah ** war ich ungeduldig, weil ich das Gesetz überhaupt nicht verstehen konnte **.
Wenn jedoch bei der Konvertierung in eine Dezimalzahl auch nur eine 0 in die Ziffern gemischt wird, ändert $ minDigit (a_n) = 0 $, und $ k \ geqq n $ ändert den Wert von $ a_k $ nicht. .. Es wird auch vorausgesagt, dass $ minDigit (a_n) = 0 $ bald erreicht wird ($ , da es unwahrscheinlich ist, dass $ bei jedem n $ minDigit (a_n) \ neq0 $ ist), also $ minDigit (a_n) = 0 Als es $ wurde, wurde $ a_k $ zu diesem Zeitpunkt ausgegeben und gebrochen.
Da es sich um ein Wettbewerbsprogrammierungsproblem handelt, gibt es eine bestimmte Anzahl von Problemen, die ohne strenge Beweise gelöst werden können. Daher möchte ich es lösen. (Obwohl es in meinem Kopf bewiesen werden sollte)
A.py
t=int(input())
for i in range(t):
a,k=map(int,input().split())
for i in range(k-1):
ax=str(a)
l,r=int(min(ax)),int(max(ax))
if l==0:
print(a)
break
else:
a+=(l*r)
else:
print(a)
B-Problem
Ich habe falsch verstanden, dass ich alle in die Gruppe aufnehmen musste ... Da nicht alle Personen in die Gruppe aufgenommen werden müssen, wählen Sie nacheinander die Personen mit der geringsten "Anzahl der für die Gruppe erforderlichen Personen" aus. Zu diesem Zeitpunkt muss die Anzahl der als Gruppe ausgewählten Personen gleich oder größer sein als die "erforderliche Anzahl von Personen in der Gruppe" jeder Person. Wenn sie also nicht größer als die "erforderliche Anzahl von Personen in der Gruppe" ist, fügen Sie der Gruppe so viele Personen wie nötig hinzu Machen. Und wenn die Gruppe die Bedingungen erfüllt, kann sie zur Anzahl der Gruppen des Subjekts hinzugefügt werden. In Python habe ich den Vortest bestanden, also war ich vorsichtig, aber es wurde TLE. Es kann zuverlässiger sein, C ++ für einen so geringen Rechenaufwand zu werfen.
B.py
t=int(input())
for i in range(t):
n=int(input())
e=sorted(list(map(int,input().split())))
ans,now=0,0
while True:
nowx=now+e[now]
while nowx<n:
if nowx-now<e[nowx-1]:
nowx=now+e[nowx-1]
else:
break
if nowx>=n:
if nowx==n:
if nowx-now>=e[nowx-1]:
ans+=1
break
else:
ans+=1
now=nowx
print(ans)
answerB.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 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.
#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
signed main(){
ll t;cin >> t;
vector<ll> answers(t);
REP(i,t){
ll n;cin >> n;
vector<ll> e(n);REP(j,n)cin >> e[j];
sort(ALL(e));
ll ans=0;ll now=0;
while(true){
ll nowx=now+e[now];
while(nowx<n){
if(nowx-now<e[nowx-1]){
nowx=now+e[nowx-1];
}else{
break;
}
}
if(nowx>=n){
if(nowx==n){
if(nowx-now>=e[nowx-1]){
ans++;
}
}
break;
}else{
ans++;
now=nowx;
}
}
answers[i]=ans;
}
REP(i,t){
cout << answers[i] << endl;
}
}
C-Problem
Ich bin froh, dass ich über dieses Problem richtig nachdenken konnte. Um als Dreieck zu halten, muss zunächst (Summe der kleinsten zwei Seiten)> (größte Seite) gelten.
Außerdem gilt $ A \ leqq x \ leqq B \ leqq y \ leqq C \ leqq z \ leqq D $ zwischen den drei Seiten des Dreiecks $ x, y, z $, also $ x + y> z $ Ich brauche es einfach. Darüber hinaus gilt $ A + B \ leqq x + y \ leqq B + C $, und es ist klar, dass dieser x + y-Kandidat in der Größenordnung von etwa $ 10 ^ 5 $ liegt, so dass x + y als Original entschieden wird. Ich dachte, ich sollte den Kandidaten für z durch $ O (1) $ finden (** Es ist natürlich zu denken, dass ich einen reparieren möchte, weil es drei Unbekannte gibt ** Als Ergebnis von Experimenten wie haben wir festgestellt, dass es besser ist, mit x + y zu fixieren.).
Wenn Sie so weit denken, können Sie herausfinden, wie viele z kleiner als x + y sind, aber hier gibt es eine Falle. Kandidaten für den Wert von x + y liegen in der Größenordnung von ungefähr $ 10 ^ 5 $, aber es gibt mehrere Paare von x und y für den Wert von x + y. Die Verarbeitung dieser verschiedenen Dinge kann gut durch Zeichnen der folgenden Abbildung gedacht werden. (Ich bin froh, dass ich diese Überlegung beruhigen konnte. Ich hatte zuvor ein ähnliches Problem mit AtCoder und konnte es nicht lösen ...)
Daher können die Kandidaten für das (x, y) -Paar gefunden werden, wenn $ x + y = k $ ist, und der Kandidat für z zu diesem Zeitpunkt ist wie in der Abbildung unten gezeigt.
Daher ist die Antwort die Summe des Produkts aus der Anzahl der Paare von (x, y), wenn $ x + y = k $, und der Anzahl der Kandidaten für z.
C.py
a,b,c,d=map(int,input().split())
xy=dict()
for i in range(a+b,b+c+1):
f=min(i-a-b+1,b+c-i+1)
f=min(f,b-a+1,c-b+1)
xy[i]=f
ans=0
for i in range(a+b,b+c+1):
if i>d:
ans+=(xy[i]*(d-c+1))
elif i<=c:
continue
else:
ans+=(xy[i]*(i-c))
print(ans)
D Problem
Ich bin mir über den Beweis nicht sicher, weil ich den Denkprozess übersprungen und das Problem gelöst habe.
Da Petya jedoch eine bequeme Sequenz erstellen kann, führt dies zu der Idee, dass Petja eine bequeme Sequenz erstellen möchte, um zu gewinnen. Es ist auch gut, wenn es für das Teilarray keine Summe von k oder Sk gibt. Wenn Sie also auf seine Symmetrie achten, ** das Teilarray, dessen Summe nahe bei 0 liegt und dessen Summe nahe bei S liegt. Ich dachte, es wäre gut, ein Array ** anzunehmen, in dem nur teilweise Arrays existieren.
Ein solches Array würde wie in der folgenden Abbildung aussehen (n in Groß- und Kleinbuchstaben), wobei zu beachten ist, dass alle Elemente des Arrays größer oder gleich 1 und kleiner oder gleich S-1 sind und die Summe aller Elemente S ist. Mach dir keine Sorgen, dass es geschlossen wird.)
Unter der Annahme eines Arrays wie dem obigen kann die Summe der Subarrays $ 1 $ ~ $ n-1, S- (n-1) $ ~ $ S $ und ** Symmetrie sein. Ich dachte, es wäre praktisch, weil es ** ist. Um diese bequeme Sequenz zu erstellen (Petya gewinnt), ist es auch ausreichend, wenn es ein k gibt, das $ n-1 <k <S- (n-1) $ erfüllt, und ein solches k existiert. Die Bedingung für ist $ n-1 <S- (n-1) $, und wenn sie implementiert ist, wird sie wie folgt (wenn $ , weil $ k dies erfüllt, ist es klar, dass Sk dies auch erfüllt. ).
answerD.py
n,s=map(int,input().split())
if n<s-(n-1):
print("YES")
print(" ".join(map(str,[1 if i!=n-1 else s-(n-1) for i in range(n)])))
print(n)
else:
print("NO")
E Problem
Ich habe einige Lösungen für die dreiminütige Suche gesehen, aber die dreiminütige Suche habe ich noch nicht durchgeführt, daher werde ich diese Zeit überspringen.
F Problem
Wie beim E-Problem denke ich, dass mir immer noch die Fähigkeiten fehlen, also werde ich diese Zeit überspringen.
Recommended Posts