[PYTHON] Educational Codeforces Round 93 Bacha Review (8/17)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich habe immer noch das Gefühl, dass der Ort, an dem D nicht passieren kann, nicht stabil ist. Ich blieb beim Versuch stecken, es mit einer nicht angenommenen Lösung zu tun. Selbst wenn Sie versuchen, verrückt zu werden, ** stellen Sie sicher, dass Sie eine gute Perspektive haben, bevor Sie sie implementieren **.
Problem A
Ich habe das Problem fast falsch verstanden. Das Problem besteht darin, einen Satz von drei Zahlen zu beantworten, die kein Dreieck bilden, und da die Folge $ a $ in aufsteigender Reihenfolge sortiert wurde, ist $ a \ _i + a \ _j <a \ _k (i <j <k) $ Stellen Sie sicher, dass es existiert. Dies kann erreicht werden, indem man erwägt, $ a \ _i + a \ _j $ kleiner und $ a \ _k $ größer zu machen. Stellen Sie also sicher, dass $ (i, j, k) = (1,2, n) $ gilt. TU es einfach.
A.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
if a[0]+a[1]<=a[-1]:
print(f"1 2 {n}")
else:
print(-1)
B-Problem
Es schien für einen Moment schwierig, aber es war einfach.
Beide zielen darauf ab, die Anzahl der zu wählenden Einsen zu maximieren, also wechseln Sie sich von der längsten fortlaufenden Unterspalte ab. Daher wird die Länge der fortlaufenden Teilzeichenfolge von 1, die in der Zeichenfolge $ S $ enthalten ist, in "ans" gespeichert und dann in absteigender Reihenfolge der Werte sortiert, und die Summe der ungeraden Reihenfolge ist der Maximalwert von Alices Punktzahl. In Python ist dies sehr praktisch, da Sie mit nur "ans [:: 2]" schreiben können, um zwei zu überspringen.
B.py
for _ in range(int(input())):
s=input()
n=len(s)
ans=[0]
for i in range(n):
if s[i]=="1":
ans[-1]+=1
else:
if ans[-1]!=0:
ans.append(0)
ans.sort(reverse=True)
print(sum(ans[::2]))
C-Problem
Ich vermutete DP wegen seiner einfachen Handhabung als Übergang der Addition, aber es ist schwierig **, weil ich den Status nicht verwalten kann ** (als Ergebnis war das D-Problem DP. Ich bin enttäuscht).
Da wir uns mit ** Intervallen befassen, haben wir uns entschlossen, den Unterschied in den kumulierten Summen ** zu berücksichtigen. Daher wird die Summe bis zum $ x $ th als $ S \ _x $ gesetzt. Zu diesem Zeitpunkt ist der Zustand des Subjekts $ S \ _r- S \ _ {l-1} = r-l + 1 \ linker rechter Pfeil S \ _r-r = S \ _ {l-1} - (l-1) $ Ich werde. Wenn also $ S \ _0-0 = 0 $ ist, wird jedes $ i (0 \ leqq i \ leqq n) $ mit demselben $ S \ _i-i $ gepaart. Daher wird dies in diejenigen unterteilt, die mit einem Wörterbuch wie Counter identisch sind, und wenn es $ l $ $ i $ gibt, so dass $ S \ _i-i = k $, $ \ _l C \ _2 $ Ist die Anzahl dieser $ i $ -Kombinationen. Führen Sie diese Berechnung für jedes $ k $ durch, und die Summe ist die Antwort.
AtCoder scheint auch kürzlich herausgekommen zu sein, so dass ich es mit hoher Geschwindigkeit lösen konnte. Wahrscheinlich hat es vor einem Monat ungefähr 30 Minuten gedauert, also spürte ich die Wichtigkeit und das Wachstum der Hingabe.
C.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
if a==[i+1 for i in range(n)]:
print(0)
continue
#Ohne die Kanten
for i in range(n):
if a[i]!=i+1:
break
for j in range(n-1,-1,-1):
if a[j]!=j+1:
break
#Indexfehler
for k in range(i,j+1):
if a[k]==k+1:
print(2)
break
else:
print(1)
D Problem
** Ich hatte das Gefühl, dass eine Lücke in einer Überlegung einen großen Unterschied macht **. Ich möchte eine genauere Überlegung machen.
Die erste Richtlinie, die Sie leicht finden können, ist **, diejenigen mit den größten Werten gierig zu kombinieren **. Mit anderen Worten, die Paare von $ r-, g- und b $ -Seiten werden in der Reihenfolge der längsten in die Priorität \ _queue verschoben, und die Paare werden aus der längsten gebildet. Wenn diese Methode verwendet wird, bleibt ** nur eine Farbseite übrig . Was soll ich in diesem Fall tun? Die erste Methode besteht darin, die zusätzlichen Seiten nachzurüsten. Da jedoch die Greedy-Methode verwendet wird ( Ich entscheide die Reihenfolge der Auswahl willkürlich **), besteht die Möglichkeit, dass die Greedy-Methode durch ** Nachrüstung ** unterbrochen wird. Ich dachte, ich würde es nicht brechen, aber ich konnte es nicht implementieren, weil ich im Begriff war, auf den Eckfall zu treten. Auf diese Weise ** ist es bis zu einem gewissen Grad schwierig zu denken, und wenn andere Richtlinien festgelegt werden können, sollten Sie eine andere Methode in Betracht ziehen **.
Hier hat die oben erwähnte gierige Methode einen beträchtlichen ** Spielraum für die Ausführungszeit **, so dass Sie daran denken können, ohne sich speziell mit der gierigen Methode zu befassen. Die nächste Methode, an die ich denken kann, ist DP. Zusätzlich zur Berücksichtigung des ** Übergangs der Auswahl ** beträgt $ r, g, b $ höchstens 200, so dass es nur ** Zustände ** von ungefähr $ R \ mal G \ mal B = 8 \ mal 10 ^ 6 $ gibt. Unter diesem Gesichtspunkt scheint DP ein sehr wirksames Mittel zu sein.
Der hier betrachtete DP ist wie folgt. Da es am besten ist, $ r, g und b $ aus den größten auszuwählen, werden wir mit der Diskussion fortfahren, vorausgesetzt, dass sie in absteigender Reihenfolge sortiert sind.
$ dp [i] [j] [k]: = $ ($ i $ Stücke von $ r $, $ j $ Stücke von $ g $, $ k $ Stücke von $ b $, das größte Rechteck Gesamtfläche)
Darüber hinaus werden wir bei einem normalen Übergang erwägen, Elemente einzeln hinzuzufügen. Dieses Mal können wir jedoch ein Rechteck erstellen, indem wir ein Paar bilden. Daher betrachten wir einen Übergang, der ** Paare ** hinzufügt. So sieht es aus:
(1) Wenn $ i <R $ und $ j <G $
Sie können ein Paar aus $ r $ und $ g $ auswählen, wählen Sie also das größte $ r [i] $ und $ g [j]
(2) Wenn $ i <R $ und $ k <B $
Sie können ein Paar aus $ r $ und $ b $ auswählen, wählen Sie also das größte $ r [i] $ und $ b [k]
(3) Wenn $ j <G $ und $ k <B $
Sie können ein Paar aus $ g $ und $ b $ auswählen, wählen Sie also das größte $ g [j] $ und $ b [k]
(4) Zu anderen Zeiten Da es als Gruppe nichts zu wählen gibt, sind die folgenden Antworten. [1] Wenn $ i <R $, ist $ dp [i + 1] [j] [k] = max (dp [i + 1] [j] [k], dp [i] [j] [k] ) $ [2] Wenn $ j <G $, ist $ dp [i] [j + 1] [k] = max (dp [i] [j + 1] [k], dp [i] [j] [k] ) $ [3] Wenn $ k <B $, ist $ dp [i] [j] [k + 1] = max (dp [i] [j] [k + 1], dp [i] [j] [k] ) $
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
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll R,G,B;cin>>R>>G>>B;
vector<ll> r(R);REP(i,R)cin>>r[i];sort(ALL(r),greater<ll>());
vector<ll> g(G);REP(i,G)cin>>g[i];sort(ALL(g),greater<ll>());
vector<ll> b(B);REP(i,B)cin>>b[i];sort(ALL(b),greater<ll>());
vector<vector<vector<ll>>> dp(R+1,vector<vector<ll>>(G+1,vector<ll>(B+1,0)));
REP(i,R+1){
REP(j,G+1){
REP(k,B+1){
//DP für jedes Paar auswählen und verteilen
//Es ist einfach, wenn Sie daran denken
//dp[i][j][k]:=Wenn das i-te j-te und das k-te gepaart sind
bool f=false;
if(i<R and j<G){
dp[i+1][j+1][k]=max(dp[i+1][j+1][k],dp[i][j][k]+r[i]*g[j]);
f=true;
}
if(i<R and k<B){
dp[i+1][j][k+1]=max(dp[i+1][j][k+1],dp[i][j][k]+r[i]*b[k]);
f=true;
}
if(j<G and k<B){
dp[i][j+1][k+1]=max(dp[i][j+1][k+1],dp[i][j][k]+g[j]*b[k]);
f=true;
}
if(!f){
if(i<R)dp[i+1][j][k]=max(dp[i+1][j][k],dp[i][j][k]);
if(j<G)dp[i][j+1][k]=max(dp[i][j+1][k],dp[i][j][k]);
if(k<B)dp[i][j][k+1]=max(dp[i][j][k+1],dp[i][j][k]);
}
}
}
}
cout<<dp[R][G][B]<<endl;
}
Nach dem E-Problem
Ich werde diesmal überspringen
Recommended Posts