[PYTHON] Codeforces Runde # 521 (Div. 3) Bacha Review (10/9)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Es war ein Problem, das bis zur F1 gelöst werden sollte, aber es machte DP fehlerhaft. Ich hatte eine grundlegende Richtlinie, aber ich habe mich gefragt, ob ich das Übergangsziel oder die Übergangsquelle ** korrigieren soll, oder ich habe einen Fehler im Index ** gemacht, also bereue ich es.
Problem A
Es war ein Problem, das ich in ABCs C-Problem sehen konnte. Wenn Sie sich eine Operation ansehen, die mit $ a $ vorwärts geht und mit $ b $ zurückkehrt, wird diese Operation $ [\ frac {k} {2}] $ mal ausgeführt. Im Fall von $ k $ rückt es am Ende noch einmal um $ a $ vor, sodass Sie die obige Summe finden können.
A.py
for _ in range(int(input())):
a,b,k=map(int,input().split())
ans=(a-b)*(k//2)
if k%2==0:
print(ans)
else:
print(ans+a)
B-Problem
Verhindert, dass die Zeichenfolge $ 101 $ angezeigt wird. Betrachten Sie für solche Probleme zuerst die ** Giermethode **.
Schauen wir uns zum Beispiel die Zeichen an, die von links $ 101 $ sein können. Das heißt, $ i $ = 1 ~ $ n-2 $ ergibt $ a [i-1: i + 2] = "101" $. Zu diesem Zeitpunkt ist es notwendig, 1 auf beiden Seiten von 0 auf 0 zu ändern. Da jedoch auf der linken Seite nichts vorhanden ist, das bereits $ 101 $ beträgt, ist es am besten, 1 auf der rechten Seite auf 0 zu ändern ** Wiederholen Sie diesen Vorgang und zählen Sie, wie oft Sie ihn auf 0 geändert haben.
B.py
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(1,n-1):
if a[i-1]==1 and a[i]==0 and a[i+1]==1:
a[i+1]=0
ans+=1
print(ans)
C-Problem
Die Richtlinie war sofort, aber ich habe einen Fehler in das Rätsel eingebettet.
Angenommen, Sie schließen ** $ a [j] $ ** aus (nehmen wir an, dass die verbleibende Zahlenspalte $ b $ ist). Zu diesem Zeitpunkt sollte $ sum (a) -a [j] = 2 \ times b \ _ {max} $ gelten. Sie können auch $ b_ {max} $ außer $ a [j] $ auswählen. Hier wird $ sum (a) $ im Voraus berechnet und $ a [j] $ angegeben. Wenn also ** $ a [j] $ angegeben wird, wird $ b \ _ {max} $ beschleunigt. Überlegen Sie, was Sie von ** wollen. Erstens, wenn es zwei oder mehr Elemente gibt, die zu $ a \ _ {max} $ werden, ** ist immer $ b \ _ {max} = a \ _ {max} $ **, also für jedes $ j $. Es kann nach $ O (1) $ beurteilt werden. Wenn es nur ein Element gibt, das zu $ a \ _ {max} $ wird, ** speichern Sie das zweitgrößte Element ** und $ a [j] = a \ _ {max} $ Nur wenn $ a [j] $ ausgeschlossen ist, sollte $ b \ _ {max} = $ (das zweitgrößte Element) gesetzt werden. Auch zu diesem Zeitpunkt kann das Urteil mit $ O (1) $ getroffen werden.
Ich konnte ein Urteil fällen, aber da ich beim Finden des größten und des zweiten Elements sortiert habe, ** unterschied sich der Index, den ich suchte, vom Thema **. Daher habe ich versucht, den Wert, der das Thema im vorherigen Urteil erfüllt, vorerst in $ set $ zu speichern und schließlich den Index des in $ set $ enthaltenen Elements zu finden.
C.py
n=int(input())
b=list(map(int,input().split()))
a=sorted(b)
s=sum(a)
ans=set()
if a[-2]==a[-1]:
ma=a[-1]
for i in range(n):
if s-a[i]==2*ma:
ans.add(a[i])
else:
ma1,ma2=a[-1],a[-2]
for i in range(n):
if i==n-1 and s-a[i]==2*ma2:
ans.add(a[i])
if i!=n-1 and s-a[i]==2*ma1:
ans.add(a[i])
realans=[]
for i in range(n):
if b[i] in ans:
realans.append(str(i+1))
print(len(realans))
print(" ".join(realans))
D Problem
Ich habe einen Fehler bei der Implementierung gemacht und war ungeduldig.
Ich werde es schneiden, aber ich berücksichtige die Reihenfolge nicht, also werde ich verwalten, wie viele jede Zahl im Wörterbuch $ c $ herauskommt. Wenn Sie zu diesem Zeitpunkt nicht wissen, wie oft Sie schneiden müssen, wissen Sie nicht, wie Sie das Element in $ t $ aufnehmen sollen. Nehmen wir daher an, wir schneiden nur ** $ x $ mal ** und fahren mit der Diskussion fort. Wenn hier die Zahl $ i $ in $ c $ nur in $ c [i] $ enthalten ist, enthält $ t $ $ i $ nur in $ \ frac {c [i]} {x} $. Kann enthalten sein. Wenn Sie dies für im Wörterbuch verwaltete $ i $ überprüfen, können Sie daher das längste $ t $ ** finden, wenn Sie ** $ x $ mal schneiden. Wenn hier die längste Länge von ** $ t $ größer oder gleich $ k $ ist, dann kann ** das Subjekt $ t $ konstruiert werden. Durch Erhöhen der Anzahl der Schnitte ** verringert sich außerdem die Länge von $ t $ monoton , so dass sie (die längste Länge von $ t $ beim Schneiden von $ x $ mal) $ \ geqq k $ wird. Ich möchte das größte $ x $ finden, also werde ich es durch Dichotomie (✳︎) finden. Sie können auch $ t [: k] $ ausgeben, wenn die erhaltenen $ x $ ( Elemente nur $ k $ ** ausgegeben werden dürfen. Beachten Sie, dass hier 1WA ).
(✳︎)… Die Dichotomie wird unter Bezugnahme auf diesen Artikel erstellt. Beachten Sie, dass die Rollen von ** $ l, r $ vertauscht sind **, da wir diesmal den Anfangswert von ** $ l, r $ ** und den Maximalwert ermitteln möchten.
D.py
n,k=map(int,input().split())
s=list(map(int,input().split()))
from collections import Counter
c=Counter(s)
z=dict()
def f(x):
global n,k,c,z
if x>n:return False
if x==0:return True
ret=0
z=dict()
for i in c:
ret+=c[i]//x
z[i]=c[i]//x
#print(x,ret)
return ret>=k
#l:True,r:False
l,r=0,10**6
while l+1<r:
y=l+(r-l)//2
if f(y):
l=y
else:
r=y
f(l)
#print(z)
ans=[]
for i in z:
for j in range(z[i]):
ans.append(str(i))
print(" ".join(ans[:k]))
E Problem
Aufgrund eines Implementierungsfehlers in C, D und E dauerte es lange. Ich werde mich widmen. Auch TL schien dieses Problem zu lösen, und ich habe es in C ++ veröffentlicht, aber es war eine richtige Wahl.
Zuerst habe ich das Problem falsch verstanden ** und es beim Betrachten der Probe bemerkt. Da $ pairwise \ different $, kann jeder Wettbewerb nur Probleme zum gleichen Thema behandeln, und Probleme zu einem Thema können nur in einem Wettbewerb enthalten sein.
Zählen Sie daher, wie viele Probleme in jedem Thema vorhanden sind, und zeichnen Sie sie einmal in der Karte auf. Da ** Themennummern nicht benötigt werden **, wird nur die Anzahl der Probleme im Array $ a $ gespeichert ($ a $ wird sortiert, der Grund wird später erläutert).
** Wenn die erste Nummer nicht entschieden wird, wird die Nummer danach nicht entschieden **, also sei die erste Nummer $ x $. Außerdem ist $ x $ mehr als 1 und weniger als $ 2 \ mal 10 ^ 5 $. Zu diesem Zeitpunkt ist die Anzahl der Fragen von $ x, 2x, 4x… $ erforderlich, um jeden Wettbewerb zu eröffnen. Da die maximale Anzahl von Fragen für jedes Thema $ 10 ^ 5 $ beträgt, beträgt die maximale Anzahl von Tagen für den Wettbewerb ungefähr $ 20 $ Tage ** ($ \ weil \ 10 ^ 5 \ <2 ^ {20} $). Ich bemerkte, dass es gab. Wenn Sie einen Wettbewerb mit $ y $ Fragen eröffnen, ist es selbstverständlich, dass Sie danach so viele Wettbewerbe wie möglich ** eröffnen können, indem Sie das Thema ** mit der geringsten Anzahl von Fragen über ** $ y $ ** auswählen. .. Wenn Sie $ a $ früher sortieren, verwenden Sie daher $ lower $ \ _ $ bound $ in $ a $, um zu zählen, ob es Themen mit der Anzahl der Probleme $ x → 2x → 4x →… $ gibt. Ich kann gehen. Wenn der Rückgabewert von $ lower $ \ _ $ bound $ $ end $ ist, können nachfolgende Wettbewerbe nicht geöffnet werden, sodass die Zählung endet. Außerdem ** können Sie keine Fragen für Wettbewerbe auswählen, die Sie bereits ausgewählt haben **. Speichern Sie daher die ausgewählten Themen in einer Variablen namens $ nxt $.
Gemäß der obigen Richtlinie kann die Anzahl der Tage, an denen der Wettbewerb für jedes $ x $ stattfinden kann und wie viele Fragen enthalten sind, mit $ O ((\ log {n}) ^ 2) $ berechnet werden. Der Gesamtbetrag der Berechnung beträgt also $ O ( Es wird n (\ log {n}) ^ 2) $. Im Fall von PyPy ist sogar $ O (n \ log {n}) $ besorgniserregend, daher habe ich es von Anfang an in C ++ geschrieben.
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 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 n;cin>>n;
map<ll,ll> b;
REP(i,n){
ll z;cin>>z;
b[z-1]++;
}
vector<ll> a;
FORA(i,b){
if(i.S!=0)a.PB(i.S);
}
sort(ALL(a));
//REP(i,SIZE(a))cout<<a[i]<<endl;
ll ans=0;
FOR(x,1,200000LL){
//Suche von nxt oder höher
ll ans_sub=0;
ll y=x;
auto nxt=a.begin();
while(true){
if(nxt==a.end())break;
nxt=lower_bound(nxt,a.end(),y);
if(nxt==a.end())break;
nxt++;
ans_sub++;
y*=2;
}
ans=max(ans,x*(1LL<<ans_sub)-x);
}
cout<<ans<<endl;
}
F1-Problem
(Die Problemstellung war schwer zu lesen.)
Sie können die DP-Ähnlichkeit sehen, sobald Sie sie sehen. Zu diesem Zeitpunkt ist mindestens ein Element, das in einer Reihe von $ k $ ($ \ leftrightarrow $ **) erneut veröffentlicht werden soll, kleiner als $ k $, und der Abstand zum nächsten Element rechts (dasselbe für das linke) beträgt weniger als $ k $. Da der Abstand zur Kante $ k-1 $ oder weniger beträgt **), ** sind Informationen zum zuletzt neu veröffentlichten Element ** erforderlich, und die Anzahl der endgültig neu veröffentlichten Elemente beträgt $ x $. Daraus wurde mir klar, dass ich auch Informationen über die Anzahl der Elemente ** $ repost $ ** benötigte. Daher wird der folgende DP eingestellt.
$ dp [i] [j] [l]: = $ (wenn die Anzahl der neu veröffentlichten Elemente bis zum $ i $ -ten Element $ j $ beträgt und das zuletzt ausgewählte Element das $ l $ -te Element ist Maximale Anzahl neu geposteter Elemente)
Betrachten Sie als nächstes den Übergang. Der Wert von $ dp $ wird mit -1 (entsprechend -INF) initialisiert, und nur $ dp [0] [1] [0] $ wird auf $ a [0] $ gesetzt.
** Betrachten Sie den Übergang mit oder ohne Auswahl dieses Elements **. Betrachten Sie das Übergangsziel in Abhängigkeit davon, ob das $ i + 1 $ -te Element basierend auf der Übergangsquelle von $ dp [i] [j] [l] $ ausgewählt werden soll. Das Folgende wird auch ausgeführt, wenn $ dp [i] [j] [l]! = -1 $.
① Bei Auswahl dieses Elements
Wenn $ i = $ 0 ~ $ k-2 $, können Sie es unabhängig vom Wert von ** $ l $ ** auswählen, sodass Sie es auswählen können, wenn $ j! = X $. Wenn $ i = k-1 $ ~ $ n-2 $ ist, muss zusätzlich zu $ j! = X $ $ (i + 1) -l \ leqq k $ sein.
Wenn $ i = $ 0 ~ $ k-2 $ ist, ist ** erforderlich, wenn das $ i + 1 $ -te Element zum ersten Mal ausgewählt wird **
Sollte zuerst gemacht werden.
② Wenn Sie dieses Element nicht auswählen
Wenn nicht ausgewählt, gibt es keine Bedingung, nur $ i $ wird um +1 erhöht.
Wenn Sie die obigen Schritte ausführen, wird dp abgeschlossen. Wenn ich nach einer Antwort suche, möchte ich auch das Maximum von $ dp [n-1] [x] [l] $ mit einem beliebigen $ l $ finden, aber ** $ n-1-l \ leqq k \ leftrightarrow l Beachten Sie, dass es \ geqq n-1-k $ ** sein muss.
F1.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 n,k,x;cin>>n>>k>>x;
vector<ll> a(n);REP(i,n)cin>>a[i];
if(k==1){
if(x!=n){
cout<<-1<<endl;
}else{
cout<<accumulate(ALL(a),0LL)<<endl;
}
return 0;
}
//Initialisierung aus irgendeinem Grund
//Wenn nicht-1
vector<vector<vector<ll>>> dp(n,vector<vector<ll>>(x+1,vector<ll>(n,-1)));
//Initialisieren(Wählst du i)
dp[0][1][0]=a[0];
REP(i,k-1){
//Bei der ersten Auswahl
dp[i+1][1][i+1]=a[i+1];
REP(j,x+1){
REP(l,n){
if(true){
if(dp[i][j][l]!=-1){
//Bei der Wahl
if(j!=x){
dp[i+1][j+1][i+1]=max(dp[i+1][j+1][i+1],dp[i][j][l]+a[i+1]);
}
//Wenn Sie nicht wählen
dp[i+1][j][l]=max(dp[i+1][j][l],dp[i][j][l]);
}
}
}
}
}
//Überleitung
FOR(i,k-1,n-2){
REP(j,x+1){
REP(l,n){
if(true){
if(dp[i][j][l]!=-1){
//Bei der Wahl
if(j!=x and (i+1)-l<=k){
dp[i+1][j+1][i+1]=max(dp[i+1][j+1][i+1],dp[i][j][l]+a[i+1]);
}
//Wenn Sie nicht wählen
dp[i+1][j][l]=max(dp[i+1][j][l],dp[i][j][l]);
}
}
}
}
}
//Reichweite hier
ll ans=-1;
FOR(l,n-1-(k-1),n-1){
ans=max(ans,dp[n-1][x][l]);
}
cout<<ans<<endl;
}
F2 Problem
Ich werde diesmal überspringen.
Recommended Posts