[PYTHON] Codeforces Runde # 610 (Div. 2) Bacha Review (10/5)
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Diesmal war es eine Parade von Fehlern wie Abhören der Implementierung und falschem Lesen. Ich würde es gerne ein bisschen mehr lösen können **, aber ich mache mir Sorgen, weil es nicht stabil ist.
Diese Woche werde ich versuchen, bacha mit der Absicht, ** immer Implementierungsfehler und Fehlinterpretationen zu reduzieren **.
Problem A
Ein Problem, aber ich habe meine Zeit verschwendet, weil ** ich die Fälle nicht gut klassifizieren konnte **.
Fälle werden durch die Positionen von $ c-r $ und $ c + r $ geteilt. Die Antwort ist auch für $ a → b $ und $ b → a $ dieselbe. Tauschen Sie also $ a $ und $ b $ aus, sodass sie immer $ a \ leqq b $ sind.
Ich möchte die Positionen von $ c-r $ und $ c + r $ kennen, daher ist es schneller, mit Zahlen als mit Worten zu erklären. Mit anderen Worten, die folgende Abbildung sollte für jeden Fall implementiert werden.
A.py
for _ in range(int(input())):
a,b,c,r=map(int,input().split())
if a>b:
a,b=b,a
ans=0
if c+r<a:
print(b-a)
elif c+r<=b:
if c-r<=a:
print(b-(c+r))
else:
print(b-(c+r)+(c-r)-a)
else:
if c-r<=a:
print(0)
elif c-r<=b:
print((c-r)-a)
#print(c-r,b)
else:
print(b-a)
B1-Problem, B2-Problem
Ich dachte, es sei nicht so schwierig, also habe ich es gemeinsam gelöst. Es war gefährlich, weil es überflutete. ** Ich bedauere, dass ich an einer unerwarteten Stelle in der Implementierung eine nutzlose Berechnung durchgeführt habe **. Überprüfen Sie es unbedingt, bevor Sie es einreichen.
Zunächst einmal ist es selbstverständlich, dass Sie von der kleineren kaufen sollten. Auf dieser Grundlage habe ich darüber nachgedacht, von (nur) $ k $ Stücken und einem mit den restriktiveren $ k $ Stücken zu kaufen, aber wenn Sie ruhig experimentieren, können Sie zuerst von einer Person kaufen. Ich weiß was zu tun ist. Wenn Sie also $ x $ Stücke kaufen möchten, ist es am besten, zuerst ** $ x \% \ k $ Stücke und dann $ xx \% \ k $ Stücke von $ k $ Stück ** zu kaufen. .. Wenn ich jedoch alle $ x $ versuche, ist es nicht rechtzeitig für $ O (n ^ 2) $. Ich dachte auch, dass es eintönig wäre und in zwei Hälften durchsucht werden könnte, aber wenn es $ k = 99 $ wäre, zum Beispiel wenn $ x = 98 $, würde ich alle 98 von vorne kaufen. Wenn $ x = 99 $, müssen Sie nur die 99. von vorne kaufen, damit Sie zeigen können, dass ** Monotonie nicht gilt ** (während des Wettbewerbs habe ich es nicht bemerkt, bis ich die Dichotomie implementiert habe. …).
Ich bemerkte auch, dass ** auf jeden Rest achten **, wenn ich zeige, dass diese Monotonie nicht gilt. Mit anderen Worten, für $ x $, dessen Rest $ a $ ist, wird es maximiert, wenn $ k $ so weit wie möglich genommen wird, um $ p $ nicht zu überschreiten. Daher kann der Maximalwert für jeden Rest erhalten werden, und der Gesamtmaximalwert sollte ausgegeben werden.
B.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 t;cin>>t;
REP(i,t){
ll n,p,k;cin>>n>>p>>k;
vector<ll> a(n);REP(i,n)cin>>a[i];
sort(ALL(a));
vector<ll> cand(k,0);
vector<ll> acc(n,0);
acc[0]=a[0];
REP(i,n-1){
acc[i+1]=a[i+1]+acc[i];
}
REP(i,k){
ll q=p;
if(i!=0){
q-=acc[i-1];
}
ll ret=0;
if(q<0)continue;
ret+=i;
REP(j,(n-i)/k){
if(a[i-1+(j+1)*k]<=q){
ret+=k;
q-=a[i-1+(j+1)*k];
}else{
break;
}
}
cand[i]=ret;
}
cout<<*max_element(ALL(cand))<<endl;
}
}
C-Problem
Ich habe es falsch verstanden und überflutet ...
In diesem Problem finden wir die maximale Anzahl von Problemen (✳︎), die gelöst werden können, nachdem ein Problem (wesentliches Problem) gelöst wurde, das $ t \ _i \ leqq s $ erfüllt, wenn es für einen bestimmten Zeitraum bei $ s $ beendet wird. Zu diesem Zeitpunkt habe ich den (✳︎) Teil falsch verstanden und dachte, dass dies die maximale Anzahl erforderlicher Probleme ist **, und ich bin in einen Zustand geraten, in dem selbst die Stichprobe nicht passte. Wie erwartet war ** die Richtlinie perfekt, daher sollte ich eine Fehlinterpretation vermuten **.
Wie auch immer, sortieren Sie alle Probleme vorerst in der Reihenfolge $ t \ _i $. Wenn Sie die Probleme bis zu $ i $ lösen möchten (wenn $ t \ i <t \ _ {i + 1} $), müssen Sie die Lösung vor ** $ t \ _ {i + 1} $ abschließen. **es gibt. Zu diesem Zeitpunkt sollten Sie so lange wie möglich verbringen und bis zu $ t \ _ {i + 1} -1 $ zum Lösen verwenden. Wenn Sie also die Zeit sparen, die zur Lösung des ersten ~ $ i $ -Problems erforderlich ist, als $ s $, müssen Sie $ s \ leqq t \ _ {i + 1} -1 $ erfüllen. Alle Probleme werden gelöst **. Außerdem ** Da mehrere Probleme zu jedem Zeitpunkt zu wesentlichen Problemen werden können, wird der Wert als Information (einfach oder schwierig) des Problems zu diesem Zeitpunkt in aufsteigender Reihenfolge zu dem Zeitpunkt gespeichert, zu dem der Schlüssel benötigt wird. Sie können es in nachschlagen. Und da wir nach dem Lösen der erforderlichen Probleme noch $ t {i + 1} -1-s $ übrig haben, haben wir ** Zeit, die verbleibenden nicht wesentlichen Probleme ** zu lösen. In dieser Zeit sollten Sie in der verbleibenden Zeit so viel wie möglich in der Reihenfolge des einfachen Problems → des schwierigen Problems unter den verbleibenden Problemen lösen (speichern Sie die Anzahl der verbleibenden einfachen und schwierigen Probleme in den Variablen $ easy, hard $). Stellen.). Aus dem oben Gesagten ergibt sich, dass die Gesamtzahl der erforderlichen und nicht wesentlichen Probleme der maximalen Anzahl von Problemen entspricht, die gelöst werden können, wenn die erforderlichen Probleme bis zum $ i $ th gelöst werden. Fragen Sie nach diesem $ i $ und Sie erhalten die Antwort.
C.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 m;cin>>m;
REP(_,m){
ll n,t,a,b;cin>>n>>t>>a>>b;
vector<ll> level(n);REP(i,n)cin>>level[i];
vector<ll> tim(n);REP(i,n)cin>>tim[i];
//Probleme, die zusätzlich gelöst werden können(Einfacher Kerl,Schwieriger Typ)
ll easy=0;ll hard=0;
//Level für die Zeit
map<ll,vector<ll>> problem;
REP(i,n){
if(level[i]==0)easy++;
else hard++;
problem[tim[i]].PB(level[i]);
}
//Der größte Punkt
ll ans=0;
//Die Gesamtzahl der Probleme jetzt
ll now=0;
//Bisher benötigte Zeit
ll s=0;
FORA(i,problem){
if(s<=i.F-1){
if(s+easy*a>i.F-1){
ans=max(ans,ll(now+(i.F-1-s)/a));
}else{
ans=max(ans,min(ll(now+easy+(i.F-1-s-easy*a)/b),now+easy+hard));
}
}
FORA(j,i.S){
if(j==0){
s+=a;
easy--;
}else{
s+=b;
hard--;
}
now++;
}
}
if(s<=t){
ans=max(ans,now);
}
cout<<ans<<endl;
}
}
Nach D Problem
Ich werde diesmal überspringen.
Recommended Posts