Codeforces Round # 673 (Div. 2) Bacha Review (10/22)
This time's results
Impressions of this time
I'm writing an article about muka because I couldn't solve the D problem because it seemed to be solved.
[Addition] If you look closely, you missed the obvious conditions. I stuck to the solution too much ... My head is too stiff ...
Problem A
Select $ i, j $ and add $ a \ _i $ to $ a \ _j $, so the maximum number of operations ** is to select the minimum $ a \ _i $ and perform the operation. Therefore, consider the maximum number of operations when operating on any $ j $ under $ i \ neq j $. Since it does not exceed $ k $, $ [\ frac {k-a \ _ j} {a \ _ i}] $ is the outstanding number of operations for each $ j $.
A.py
for _ in range(int(input())):
n,k=map(int,input().split())
a=list(map(int,input().split()))
m=min(a)
l=a.index(m)
ans=0
for i in range(n):
if i!=l:
ans+=(k-a[i])//m
print(ans)
Problem B
$ f (b) = (total number of pairs of $ i \ <j $ such that b \ _i + b \ _j $ = $ T $), and $ f ($ f of $ c, d $ divided by $ a $) Consider minimizing c) + f (d) $. At this point, I thought that if you put ** $ x $ in an array different from $ T-x $, ** both can be set to 0.
If it is $ x \ neq Tx $, it will always hold, but if there are three or more $ x $ such as ** $ x = Tx \ leftrightarrow x = \ frac {T} {2} $ ** $ X = \ frac {T} {2} $ elements that cannot be set to 0 are $ k $, and $ c and d $ are $ \ frac {k} {2}, k- \ frac, respectively. When sorting {k} {2} $ pieces at a time, $ f (c) + f (d) $ is the minimum.
Therefore, the following cases are classified.
(1) When $ T $ is odd Put elements under $ [\ frac {T} {2}] $ in $ c $ and elements larger than $ [\ frac {T} {2}] $ in $ d $.
(2) When $ T $ is even ** $ [] with elements less than $ [\ frac {T} {2}] $ in $ c $ and elements larger than $ [\ frac {T} {2}] $ in $ d $ index the element of frac {T} {2}] $ once in $ cand $ **. Since the size of $ cand $ is $ k $, we will allocate $ \ frac {k} {2} and k- \ frac {k} {2} $ to $ c and d $ respectively.
B.py
for _ in range(int(input())):
n,t=map(int,input().split())
a=list(map(int,input().split()))
ans=[-1]*n
cand=[]
for i in range(n):
if t%2==0:
if a[i]<t//2:
ans[i]=0
elif a[i]>t//2:
ans[i]=1
else:
cand.append(i)
else:
if a[i]<=t//2:
ans[i]=0
else:
ans[i]=1
l=len(cand)
for i in range(l):
if i<l//2:
ans[cand[i]]=0
else:
ans[cand[i]]=1
print(" ".join(map(str,ans)))
C problem
It was a little tedious to implement, but it's just implemented. I think the policy is easier to establish than B.
Find the smallest element in any contiguous subsequence of $ k $ in length with any $ k $. First of all, it is self-evident that ** $ k $ decreases monotonically as it grows. At this time, paying attention to the timing when each value comes out (** main customer fall! **), ** the smallest length of the continuous subsequence of the length $ k $ that satisfies the condition of a certain value. I thought I should ask for $ k $ **.
Therefore, there is a set of indexes $ x \ _1, x \ _1,…, x \ _l $ (0-indexed in ascending order) that has a certain value of $ x $, and $ x \ _ 0 = -1, x \ _ { When l + 1} = n $, $ x \ _ {i + 1} -x \ _i \ leqq mi $ should hold for any $ 0 \ leqq i \ leqq \ {l} $. Therefore, $ mi = max (x \ _ {i + 1} -x \ _ i) $ is the solution. (I think it's easy to see the conditions for establishing ** drawing a diagram **.)
Therefore, since the minimum length of the subject can be obtained from each value ($ O (n) $), we will consider finding the minimum element that will be the answer. In other words, the implementation looks like this:
$ values $ = (an array of <values, minimum continuous subsequence length> pairs stored in ascending order of values) $ now $ = (longest length with no fixed minimum element) $ ans [i] $ = (the smallest element in any contiguous subsequence of length $ i + 1 $)
** You can decide in order from the smallest element **, so consider looking at the $ i $ th element of $ values $ in ascending order of $ i $. At this time, when $ values [i] .S $ is less than $ now $, $ now $ to $ values [i] .S $ should be $ values [i] .F $. Then $ now $ is updated to $ values [i] .S-1 $. Also, if $ values [i] .S $ is larger than $ now $, you can look at the next element of $ values $ without performing the update process. Also, if there is a subsequence of length $ k $ for which the smallest element cannot be determined, $ ans [k-1] $ must be set to -1, so $ ans $ is initially initialized with -1. I will leave it.
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 endings)、のどちら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(){
//Output specification of decimal digits
//cout<<fixed<<setprecision(10);
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(_,t){
map<ll,vector<ll>> m;
ll n;cin>>n;
REP(i,n){
ll a;cin>>a;
m[a].PB(i);
}
vector<pair<ll,ll>> values;
FORA(i,m){
ll s=SIZE(i.S);
ll mi=-1;
REP(j,s){
if(j==0){
mi=max(mi,i.S[j]+1);
}
if(j==s-1){
mi=max(mi,n-i.S[j]);
}
if(j!=s-1){
mi=max(mi,i.S[j+1]-i.S[j]);
}
}
values.PB(MP(i.F,mi));
}
vector<ll> ans(n,-1);
ll sv=SIZE(values);
#if 0
REP(i,sv){
if(i==sv-1)cout<<values[i].F<<" "<<values[i].S<<"\n";
else cout<<values[i].F<<" "<<values[i].S<<endl;
}
cout<<endl;
#endif
ll now=n;
REP(i,sv){
while(values[i].S<=now){
ans[now-1]=values[i].F;
now--;
}
}
REP(i,n){
if(i==n-1)cout<<ans[i]<<"\n";
else cout<<ans[i]<<" ";
}
}
}
D problem
You can operate it freely for less than $ 3n $ times, so consider ** when it is convenient **. The first thing to notice is that you can adjust the value by setting ** $ i = 1 $ **. Also, I thought that it could not be achieved when ** $ \ sum_ {i = 1} ^ {n} {a \ _i} $ was a multiple of $ n $ **, and it could be achieved in other cases.
Here, when $ i = 1 $ is selected, $ a \ _1 $ changes in the decreasing direction, so I think it would be better to collect as many elements as possible in ** $ i = 1 $ and then sort them **. (I couldn't finish the discussion from here).
Also, when moving an element from $ a \ _i $ to $ a \ _1 $, $ a \ _i $ will be left over by $ a \ _i \ mod \ i $. Here, ** To move this remainder to $ a \ _1 $ ** Once you move $ i-a \ _i \ mod \ i $ from $ a \ _1 $ to $ a \ _i $ , You can achieve $ a \ _i = 0 $ by moving from $ a \ _i $ to $ a \ _1 $ again. At this time, $ a \ _1 \ geqq i-1 \ geqq i- a \ _i \ mod \ i $ must be satisfied, but in ascending order of ** $ i $, $ a \ _i $ to $ a \ _1 $ Assuming that the element is moved to **, this condition is satisfied from $ a \ 1 = \ sum {j = 1} ^ {i-1} a \ _i \ geqq i-1 $.
Therefore, the above is done in ascending order of $ i $ to make $ a \ 1 = \ sum {i = 1} ^ {n} {a \ _i} $ (maximum $ 2 (n-1) $ times) and then any About $ i $ Move elements from $ a \ _1 $ to $ a \ i $ by $ b (= \ frac {\ sum {i = 1} ^ {n} {a \ _ i}} {n}) $ By letting (up to $ n-1 $ times), all elements can be equalized to $ b $ up to $ 3 (n-1) $ times in total.
D.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
ans=[]
if sum(a)%n!=0:
print(-1)
continue
b=sum(a)//n
for i in range(1,n):
if a[i]%(i+1)==0:
ans.append([i+1,1,a[i]//(i+1)])
a[0]+=a[i]
a[i]=0
else:
x=i+1-a[i]%(i+1)
ans.append([1,i+1,x])
a[0]-=x
a[i]+=x
ans.append([i+1,1,a[i]//(i+1)])
a[0]+=a[i]
a[i]=0
for i in range(1,n):
ans.append([1,i+1,b])
l=len(ans)
print(l)
for i in range(l):
print(" ".join(map(str,ans[i])))
After the E problem
I will skip this time.
Recommended Posts