Educational Codeforces Round 94 Bacha Review (9/3)
This time's results
Impressions of this time
The time has melted infinitely because I spent a lot of time on the B problem. As a reflection of problem B, I have just tried to solve it analytically. ** I think that I could solve it if I intuitively performed the greedy method **, so I regret it.
Problem A
Do you alternate 01 when you first see it? I thought that, but I felt it was troublesome because the position would shift. Therefore, I thought that it would be good if all the characters were the same so as not to depend on the position **. At this time, the condition in question shows that ** every string contains $ s [n] $ **. Therefore, if you create a string by connecting $ n $ of this character, the character corresponding to $ s [n] $ will be equal to any string. So this is the answer.
A.py
for _ in range(int(input())):
n=int(input())
s=input()
print(n*s[n-1])
Problem B
As you can see in the impression, it can be solved by ** normal greedy algorithm **.
Keep in mind that it is best to choose from the lightest ones to choose as many as possible. Also, $ s \ leqq w $ (otherwise swap the value). First, select ** what you take away **, but depending on the combination, it may be better to save heavy ones, so I am only $ i (0 \ leqq i \ leqq cnts) $ lighter ones. Suppose you choose. Also, at this time, it is necessary to satisfy $ i \ times s \ leqq p $. Below this, the number of heavier ones you can choose is $ min (\ frac {p-i \ times s} {w}, cntw) $. Also, since it is easy to find out how many of each thing is left, ** your followers should be greedily selected in order from the lightest one **. Therefore, the number of things that can be stolen when $ i $ is set is calculated by $ O (1) $, and it is possible to write a sufficiently fast program.
B.py
for _ in range(int(input())):
p,f=map(int,input().split())
cnts,cntw=map(int,input().split())
s,w=map(int,input().split())
if s>w:
s,w=w,s
cnts,cntw=cntw,cnts
ans=0
for i in range(cnts+1):
if i*s>p:break
ans_sub=0
nows=cnts-i
ans_sub+=i
#s is selected
rest1=p-i*s
#w
noww=cntw-min(rest1//w,cntw)
ans_sub+=min(rest1//w,cntw)
#Next person
#s
ans_sub+=min(f//s,nows)
rest2=f-min(f//s,nows)*s
#w
ans_sub+=min(noww,rest2//w)
ans=max(ans,ans_sub)
print(ans)
C problem
Since $ s $ is given, ** $ w $ will be restored **. Here, when $ s \ _i = 1 $, $ w $ is restored on the condition that either $ w \ _ {ix} = 1 $ or $ w \ _ {i + x} = 1 $ holds. Since it is difficult, $ w $ from the condition that both $ w \ _ {ix} = 1 $ and $ w \ _ {i + x} = 1 $ hold when ** $ s \ _ i = 0 $ ** I decided to restore.
Also, although part of $ w $ is not restored by this method, all the part that has not been restored so as to satisfy the condition ** $ s \ _i = 1 $ is set to 1 **. From the above, we were able to restore $ w $, but we do not know if it can actually be transformed from $ w $ to $ s $, so we need to confirm whether it can be transformed at the end.
C.py
for _ in range(int(input())):
s=list(map(int,input()))
x=int(input())
n=len(s)
w=[1]*n
for i in range(n):
if s[i]==0:
if i-x>=0:
w[i-x]=0
if i+x<n:
w[i+x]=0
t=[1]*n
for i in range(n):
g=0
if i-x>=0:
if w[i-x]==1:
g+=1
if i+x<n:
if w[i+x]==1:
g+=1
if g>0:
t[i]=1
else:
t[i]=0
if s==t:
print("".join(map(str,w)))
else:
print(-1)
D problem
I became impatient with MLE, but I was relieved to finish solving it in time. ** I have devised such things as converting pair <ll, ll> to ll and changing ll to ʻint` **.
I felt that this problem was not so difficult to consider and was a little troublesome to implement.
Look for $ i, j, k, l $ such that $ a \ _i = a \ _k $ and $ a \ _j = a \ _l $ hold under $ i <j <k <l $. At this time, I noticed that ** $ (a \ _ i, a \ _ j) = (a \ _ k, a \ _l) $ holds **. Also, since $ n $ has at most 3000 ways, all pairs of $ _ {3000} C_2 $ can be generated. Also, the same set is put together by map. In other words, let's assume that $ m $ is a map object, key is a pair of two elements, and value is a vector, and the pair of indexes that are the two elements is included.
Under this, $ (a \ _i, a \ _j) = (a \ _ k, a \ _l) $ must be ** $ a \ _ j <a \ _k $ **. Therefore, for each pair of two elements, use upper_bound to find the number that satisfies this. However, it takes a linear time to know the index if you use the distance function, so ** implement a binary search by yourself and return the index **. For the implementation of binary search, I referred to my this article.
D.cc
//Debugging options:-fsanitize=undefined,address
//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef int 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 4000 //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
//MLE
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(_,t){
ll n;cin>>n;
vector<ll> a(n);
REP(i,n)cin>>a[i];
//Managed by each value
map<ll,vector<ll>> m;
REP(i,n){
FOR(j,i+1,n-1){
m[a[i]*MOD+a[j]].PB(i*MOD+j);
}
}
long long ans=0;
FORA(i,m){
//Binary search
ll m=SIZE(i.S);
REP(j,m-1){
ll l,r;l=j+1;r=m-1;
if(i.S[j]%MOD<ll(i.S[l]/MOD)){
ans+=(m-j-1);
continue;
}
if(i.S[j]%MOD>=ll(i.S[r]/MOD)){
continue;
}
while(l+1<r){
ll k=l+(r-l)/2;
if(ll(i.S[k]/MOD)>i.S[j]%MOD){
r=k;
}else{
l=k;
}
}
ans+=(m-r);
}
}
cout<<ans<<endl;
}
}
E problem
Recursion is easily MLE with PyPy, why ... Anyway, ** I will write recursion in C ++ **.
Perform the following two operations.
(1) An operation that selects a certain section and reduces the number included in that section by one (however, there is at least one of each)
② Select one number and set the number to 0.
Consider the minimum number of operations when performing these operations and emptying all the sequences. The operation of ② can be easily obtained by simply calculating the number of operations for the length of the section. On the other hand, the operation of ① is a little complicated as follows.
For operation (1), it is best to select the section as long as possible. I won't prove it this time, but I feel that the pattern ** that you only have to select the whole when you select a section and perform an operation ** appears frequently (this time, you can reduce the number of operations by narrowing the section. I thought it wasn't intuitive, so I proceeded with this policy. ** It should be valid **, but ...).
In addition, when performing the operation of ①, perform the operation at the minimum of the section, not ** 1 at a time **. In addition, there is an element that becomes 0 after the operation, and the entire section cannot be operated as it is from the operation condition of ** ① **, so ** Find the minimum number of operations for each section divided by DFS * *.
So, considering the DFS implementation:
(1) When the length of the given interval $ x $ is 1.
The number of elements included in the interval $ x $ (number of operations in ①) and $ min $ in 1 (number of operations in ②) are taken and returned.
(2) When the length of the given interval $ x $ is greater than 1.
The length of the interval is $ l $, the minimum number among the numbers included in the interval is $ m $, the return value is $ ret = 0 $, and the vector that substitutes the divided intervals is $ nex = $ { }will do.
Below this, we will look at $ x [i] $ with $ i = $ 0 ~ $ l $ -1, but when $ x [i]! = M $, we can substitute it for nex. Also, when $ i = l $ -1, the interval is fixed, so call dfs with nex as the interval and add the return value to ret. When $ x [i] = m $, if $ nex $ is not empty, the interval is fixed, so call dfs with $ nex $ as the interval and add the return value to ret. At this time, leave $ nex $ empty for the next interval.
You can find the solution just by performing the above DFS. Also, if DFS is not perfected, problems of this magnitude will be a problem, so I would like to devote myself to it.
E.cc
//Debugging options:-fsanitize=undefined,address
//Compiler optimization
#pragma GCC optimize("Ofast")
//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef int 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
ll dfs(vector<ll>& x){
ll l=SIZE(x);
//If 0
if(l==1)return min(1,x[0]);
ll m=*min_element(ALL(x));
ll ret=m;
vector<ll> nex;
REP(i,l){
if(x[i]!=0){
nex.PB(x[i]-m);
if(i==l-1)ret+=dfs(nex);
}else{
if(SIZE(nex)){
ret+=dfs(nex);
nex.clear();
}
}
}
return min(ret,l);
}
signed main(){
ll n;cin>>n;
vector<ll> a(n);REP(i,n)cin>>a[i];
cout<<dfs(a)<<endl;
}
After the F problem
I will skip this time
Recommended Posts