Codeforces Round # 610 (Div. 2) Bacha Review (10/5)
This time's results
Impressions of this time
This time it was an on-parade of mistakes such as bugging the implementation and misreading. I'd like to be able to solve it a little more **, but I'm worried because it's not stable.
This week, I'll try to bacha with an awareness of ** always reducing implementation bugs and misreading **.
Problem A
A problem, but I wasted my time because ** I couldn't separate the cases well **.
Cases are divided by the positions of $ c-r $ and $ c + r $. Also, the answer is the same for $ a → b $ and $ b → a $, so swap $ a $ and $ b $ so that they are always $ a \ leqq b $.
I want to know the positions of $ c-r $ and $ c + r $, so it is faster to explain with a figure than words. In other words, the figure below should be implemented for each case.
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
I thought it wasn't that difficult, so I solved it together. It was dangerous because it was swamping. ** I regret that I made a useless calculation in an unexpected place in the implementation **. Be sure to review it before submitting.
First of all, it is self-evident that you should buy from the smaller one. Based on this, I thought about buying from (just) $ k $ pieces and one with the more restrictive $ k $ pieces, but if you experiment calmly, you can buy from one person first. I know what to do. So if you want to buy $ x $ pieces, it's best to buy ** $ x \% \ k $ pieces first and then $ xx \% \ k $ pieces by $ k $ pieces ** .. However, when I try all $ x $, it is not in time for $ O (n ^ 2) $. Also, I thought that it would be monotonous and could be a binary search, but if $ k = 99 $, for example, if $ x = 98 $, I would buy all 98 from the front. If $ x = 99 $, you only have to buy the 99th one from the front, so you can show that ** monotonicity doesn't hold ** (during the contest, I didn't notice until I implemented binary search). …).
I also noticed that ** pay attention to each remainder ** when showing that this monotonicity does not hold. In other words, for $ x $ whose remainder is $ a $, it is maximized when $ k $ is taken as much as possible so as not to exceed $ p $. Therefore, the maximum value for each remainder can be obtained, and the total maximum value should be output.
B.cc
//Debugging options:-fsanitize=undefined,address
//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#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 is a container such as vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
signed main(){
//Code for speeding up input
//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
I misread it and swamped ...
In this problem, we will find the maximum number of problems (✳︎) that can be solved after any problem (essential problem) that satisfies $ t \ _i \ leqq s $ when exiting at $ s $ for a certain time has been solved. At this point, I misread the (✳︎) part and thought that it was the maximum number of required problems **, and I fell into a state where even the sample did not fit. As expected, ** the policy was perfect, so I should suspect misreading **.
Anyway, sort any problems in the order of $ t \ _i $ for the time being. Here, if you want to solve the problem up to $ i $ (when $ t \ i <t \ _ {i + 1} $), you need to finish solving before ** $ t \ _ {i + 1} $. **there is. At this time, it is good to spend as long as possible, and solve using up to $ t \ _ {i + 1} -1 $. Therefore, if you save the time required to solve the 1st ~ $ i $ problem as $ s $, it is required to satisfy $ s \ leqq t \ _ {i + 1} -1 $. All the problems will be solved **. Also, ** Since multiple problems may become essential problems at each time, value is saved as information (easy or difficult) of the problem at that time in ascending order at the time when key is required. You can look it up in. And since we have $ t {i + 1} -1-s $ left over after solving the required problems, we have ** time to solve the remaining non-essential problems **. In this time, you should solve as much as possible in the remaining time in the order of simple problem → difficult problem among the remaining problems (the number of remaining easy and difficult problems is saved in the variables $ easy, hard $. Put.). From the above, the total number of required and non-essential problems is equal to the maximum number of problems that can be solved when solving the required problems up to the $ i $ th. Ask for this for any $ i $ and you'll get the answer.
C.cc
//Debugging options:-fsanitize=undefined,address
//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//for loop
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
//FORA is a range for statement(If it's hard to use, erase it)
#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 is a container such as vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
signed main(){
//Code for speeding up input
//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];
//Problems that can be solved additionally(Easy guy,Difficult guy)
ll easy=0;ll hard=0;
//Level for time
map<ll,vector<ll>> problem;
REP(i,n){
if(level[i]==0)easy++;
else hard++;
problem[tim[i]].PB(level[i]);
}
//The biggest point
ll ans=0;
//The total number of problems now
ll now=0;
//Time required so far
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;
}
}
After D problem
I will skip this time.
Recommended Posts