# 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=*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=*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`

``````

//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`

``````

//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);
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