Codeforces Round # 481 (Div. 3) Bacha Review (9/24)
This time's results
Impressions of this time
This time I was able to pass it without much bugs. It's a good trend, so I'll continue to do my best.
There was a part that got stuck, but I would like to do my best with the goal of being able to make a stable move like this one every time.
Problem A
Seen from the right side of the sequence, ** make sure that the same number does not appear twice **. Therefore, look at the numbers from the right side of the sequence and save which number appears in $ s $ of the set. At this time, if it is not included in $ s $, insert it into the array ʻans` output in the answer, and if it is included, look at the next number.
A.py
n=int(input())
a=list(map(int,input().split()))[::-1]
s={a[0]}
ans=[str(a[0])]
for i in range(1,n):
if a[i] not in s:
s.add(a[i])
ans.append(str(a[i]))
print(len(ans))
print(" ".join(ans[::-1]))
Problem B
The string can be divided into continuous and non-consecutive parts of $ x $ as shown below.
If the length $ l $ of the continuous part of this ** $ x $ can be set to 2 or less **, the subject is satisfied. Also, the minimum number of deletions required for this is $ min (0, l-2) $, so check how long $ x $ is continuous. Here, you can easily find the continuous part of ** $ x $ by using the groupby function ** as follows.
B.py
from itertools import groupby
n=int(input())
s=[]
for i in groupby(input(),lambda x:x=="x"):
s.append(list(i[1]))
#s=list(groupby(input(),lambda x:x=="x"))
ans=0
for i in s:
if i[0]=="x":
ans+=max(0,len(i)-2)
print(ans)
C problem
It is a problem to ** restore each dormitory number and room number in the dormitory ** from the room number for all dormitories. For the time being, I wrote down the room numbers for all the dormitories as follows in order to understand what the numbers are.
Also, paying attention to the ** room with the smallest room number ** in each dormitory, $ 1 \ rightarrow 1 + a \ _1 \ rightarrow 1 + a \ _1 + a \ _2 \ rightarrow… \ rightarrow 1 + a \ _1 + Since it is the cumulative sum of a \ _2 +… + a \ _ {n-1} $, save this as the array $ s $. At this time, if the given room number is $ b \ _i $, which dormitory you are in will correspond to the index of the largest element in the array $ s $ below $ b \ _i $ ** ( $ bisect $ _ $ right $). Also, the room number in the dormitory only needs to be considered from $ b \ _i $, which is the difference from the largest factor obtained earlier.
If you do the above for any $ i $, you can solve this problem with $ O (m \ log {n}) $.
C.py
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
from itertools import accumulate
s=list(accumulate([1]+a))[:-1]
from bisect import bisect_right
#print(s)
ans=[]
for i in range(m):
c=bisect_right(s,b[i])-1
#print(c)
ans.append(str(c+1)+" "+str(b[i]-s[c]+1))
for i in range(m):
print(ans[i])
D problem
It's a problem I could see, but I was able to implement the code quite quickly, so I felt a little about the recent achievements of the bacha.
If you think greedily, you have a lot of freedom, so I decided to ** fix somewhere **. At this time, I decided to ** fix both ends **. At this time, there are a total of 9 cases where both ends of $ a [0] and a [n-1] $ do not change either $ -1,0 or + 1 $.
Therefore, we will consider defining a function $ check $ that returns the number of operations based on the changes at both ends. First, to make an arithmetic progression for $ a [0], a [n-1] $ after the change as the subject, ** $ abs (a [n-1] -a [0]) $ Must be a multiple of $ n-1 $ ** (returns $ inf $ if it is not a multiple of $ n-1 $). At this time, the ** tolerance is $ \ frac {a [n-1] -a [0]} {n-1} $ **. Therefore, $ a [1] -a [0], a [2] -a [1],…, a [n-1] -a [n-2] $ are all $ \ frac {a [n-1] ] -a [0]} {n-1} $ We will greedily check whether it will be ** from the front **. At this time, if either $ + 1 or -1 $ is changed and it becomes $ \ frac {a [n-1] -a [0]} {n-1} $, the change is greedily performed. , Count the operations to change. Also, if there is an element whose tolerance is not $ \ frac {a [n-1] -a [0]} {n-1} $ for any change of $ + 1,0, -1 $, that time Returns $ inf $. If all of the above judgments are cleared, the number of counted operations is returned.
From the above, the number of operations in each of the 9 ways can be calculated, and the minimum value is output. Also, if ** the minimum value is $ inf $ **, the condition is not met, so -1 is output.
Also, please note that if you implement it yourself, you may make a mistake ** not counting the number of operations at both ends **. Furthermore, I thought it would be troublesome to classify the cases, so in the case of ** $ n = 1,2 $, I output 0 first **. In addition, I felt like I was going to make a mistake if the tolerance was negative, so in that case I ** flipped it to make the tolerance non-negative.
D.py
n=int(input())
b=list(map(int,input().split()))
if n==1 or n==2:
print(0)
exit()
inf=10**12
#x,y is the amount of change(0,-1,+1),9 ways
def check(x,y):
global b,n
ret=0
if x!=0:
ret+=1
if y!=0:
ret+=1
a=[i for i in b]
a[0]+=x
a[n-1]+=y
#In ascending order
if a[n-1]<a[0]:
a=a[::-1]
if (a[n-1]-a[0])%(n-1)!=0:
return inf
d=(a[n-1]-a[0])//(n-1)
for i in range(n-1):
if a[i+1]-a[i]==d:
pass
elif a[i+1]-a[i]==d+1:
a[i+1]-=1
ret+=1
elif a[i+1]-a[i]==d-1:
a[i+1]+=1
ret+=1
else:
return inf
return ret
ans=inf
for i in range(-1,2):
for j in range(-1,2):
ans=min(ans,check(i,j))
#print(i,j,check(i,j))
if ans==inf:
print(-1)
else:
print(ans)
E problem
There was a case I forgot to think about, and I issued 2WA, so I regret it. If you think calmly, it should have been suppressed to at least 1WA.
First of all, in order to think about what kind of value is valid, first consider the condition as ** with only ** $ x $ people. At this time, the change in the number of people at the $ i $ th bus stop is $ a \ _i $, so after passing each bus stop, $ x + a \ _0, x + a \ _0 + a \ _1,…, x + a Only \ _0 + a \ _1 +… + a \ _ {n-1} $ is on board. Therefore, you can see that ** all of these should be 0 or more and $ w $ or less ** (✳︎). Therefore, $ a \ _0, a \ _0 + a \ _1,…, a \ _0 + a \ _1 +… + a \ _ {n-1} $ is calculated by the cumulative sum, and the maximum and minimum values in this are calculated. Let's say $ u and d $ respectively. Here, if $ x + u \ leqq w $ and $ x + d \ geqq 0 $ are satisfied, (✳︎) will be satisfied when passing any bus stop (** Pay attention only to the maximum and minimum values! **). You also need to meet ** $ 0 \ leqq x \ leqq w $ ** (it was 2WA because I forgot this, sorry). Therefore, $ x + u \ leqq w $ and $ x + d \ geqq 0 $ and $ 0 \ leqq x \ leqq w $ are satisfied, so if you merge them all **, $ max (0, -d) You can find the number of integers $ x $ that satisfy \ leqq x \ leqq min (w, wu) $, and if you consider ** even if there is no intersection **, $ min (0, min (w, wu) wu) ) -Max (0, -d) + 1) $.
(The above is a comprehensive discussion and the implementation is simple, but during the contest it was ** dirty implementation and consideration **. I regret it.)
E.py
n,w=map(int,input().split())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
u,d=max(b),min(b)
print(max(0,min(w,w-u)-max(0,-d)+1))
E2.py
#Implementation during the contest
n,w=map(int,input().split())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
u,d=max(b),min(b)
if u-d>w:
print(0)
exit()
if u>w:
print(0)
exit()
ran=[max(0,-d),min(w,w-u)]
if ran[1]<ran[0]:
print(0)
exit()
print(ran[1]-ran[0]+1)
F problem
It was dangerous because I misread it at the beginning. First, as a problem setting, if there are two people, $ a and b $, and $ r \ _a > r \ _b $ and $ a and b $ are not arguing, $ a $ will be the mentor of $ b $. can.
Here, if only the first condition is used, it can be easily obtained by fetching the index with $ bisect $ _ $ left $ by having ** $ r $ values in ascending order ** (** Large and small). Are counted in ascending order! **). Also, if you add the second condition after considering the first condition, you can see that ** excluding those who are arguing while satisfying one condition **.
Therefore, the number of people that the $ i $ th person ($ r \ _i $) can mentor is ** (the number of people with lower skills than ① $ r \ _i $)-(② $ r \ _i $ The number of people who have low skills but are arguing) **. Also, $ check [i]: = $ (the number of people whose skills are lower than $ r \ _i $ in the $ i $ th person arguing), $ p: = $ (skills of each person) If you put an array of), $ check $ will be counted when you receive a set of arguers, and $ p $ will just sort the input. Therefore, ① corresponds to the index (0-indexed) when $ bisect $ _ $ left (p, r \ _ i) $ is applied, and ② corresponds to $ check [i] $.
From the above, move $ i $ in order, store the answer in the array $ ans $, and finally output it as the answer. The amount of calculation is $ O (k + n \ log {n}) $.
F.py
n,k=map(int,input().split())
r=list(map(int,input().split()))
check=[0]*n
for i in range(k):
x,y=map(int,input().split())
x-=1
y-=1
if r[x]>r[y]:
check[x]+=1
if r[y]>r[x]:
check[y]+=1
from bisect import bisect_left
ans=[0]*n
p=sorted(r)
for i in range(n):
b=bisect_left(p,r[i])
ans[i]=str(b-check[i])
print(" ".join(ans))
G problem
I wondered if there was too much room for calculation and the problem statement was long, but I missed the beat just by implementing it. Also, even though I only implemented it, it took about 30 minutes to solve it, so I would like to make an effort to pass it in about half the time.
First, the following two points are often overlooked from the problem statement.
・ You cannot take multiple exams in one day, but there is no such input due to problem restrictions. ・ Preparation does not have to be continuous
At this time, I thought that I could go with the greedy algorithm ** that prepares from the exam that is closest to the exam date. This greedy algorithm is correct because there is no benefit in preparing distant exam dates first. This can also be shown by the fact that even if a distant test date is prepared first, it will be replaced with a preparation for a closer test date **. Therefore, we will implement this greedy algorithm below.
First, prepare the following four data structures. The reasons why each is necessary will be described later. Also, you need to initialize ① and ②, but I won't explain this because it can be easily processed after receiving the input.
① Array $ exams [i]: = $ (Array holding the test (test date, required number of preparation days) for which preparation can be started on the $ i $ day) ② Array $ ind [i]: = $ ($ i $ day is the order of receipt of the test on the test date, but -1 if there is no test date) ③ Array $ ans [i]: = $ (answer to be output on the $ i $ day) ④ Set $ cand: = $ (array holding the ready test (test date, required number of preparation days))
First, prepare ④ ** to be held in ascending order of the test date in order to prepare for the test that is close to the test date. This allows you to prepare from the smallest element of $ cand $ on each day. Also, more exams will be available for new preparations on the ** $ i $ day **. All you have to do is insert ① into $ cand $ and insert all the contents of $ exams [i] $. Next, ** if that day is the test day ** is not ready, so consider the next day with $ ans [i] $ as $ m + 1 $. This can be determined by whether $ ind [i] $ is -1 if ② is prepared, and if $ ind [i] $ is not -1, consider the following operation.
We will consider ** preparing ** based on the above judgment, but $ cand $ may be empty. In this case, we are not ready, so consider the next day with $ ans [i] = 0 $. Then get ready. When preparing, you only need to look at the minimum $ cand $ exam ** (the implementation was slightly increased because you didn't notice it during the contest). Also, if ** the test date of the test has already passed **, the preparation is not in time, so -1 is output and the program is terminated. In other cases, you can take measures for the test and substitute $ ind $ for the input order of the test in $ ans [i] $. If you still need to prepare after preparing for the test, delete it from ** $ cand $, decrement the required number of preparation days by -1, and insert it again **.
After doing the above on all days, you can output $ ans $, but you have to consider the possibility that there are still elements in ** $ cand $ **. In this case, ** is synonymous with some tests that are not ready in time **, so -1 is output. In all other cases, $ ans $ is output because the test preparation is in time for all tests.
(The code below is implemented so as not to be wasteful, and the above consideration is also not wasteful, but during the contest it was a code that could make a lot of mistakes such as ** conditional branching **. It works with reflexes. Is also good, but it may be better to implement it after deepening the consideration a little more.)
G.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 n,m;cin>>n>>m;
vector<vector<ll>> exams(n);
//For the day when it's ready
vector<vector<pair<ll,ll>>> preparation(n);
//Ind for test date
vector<ll> ind(n,-1);
REP(i,m){
ll s,d,c;cin>>s>>d>>c;
exams[i]={s-1,d-1,c};
ind[d-1]=i;
preparation[s-1].PB(MP(d-1,c));
}
vector<ll> ans(n,-1);
set<pair<ll,ll>> cand;
REP(i,n){
REP(j,SIZE(preparation[i])){
cand.insert(preparation[i][j]);
}
if(ind[i]!=-1){
ans[i]=m+1;
continue;
}
if(SIZE(cand)==0){
ans[i]=0;
continue;
}
auto j=cand.begin();
while(j!=cand.end()){
if(j->S==0){
j=cand.erase(j);
}else{
if(j->F<i){
cout<<-1<<endl;
return 0;
}
ans[i]=ind[j->F]+1;
pair<ll,ll> p=*j;p.S-=1;
cand.erase(j);
if(p.S!=0){
cand.insert(p);
}
break;
}
}
if(ans[i]==-1)ans[i]=0;
}
if(SIZE(cand)==0){
REP(i,n){
if(i==n-1)cout<<ans[i]<<endl;
else cout<<ans[i]<<" ";
}
}else{
auto j=cand.begin();
while(j!=cand.end()){
if(j->S!=0){
cout<<-1<<endl;
return 0;
}
}
REP(i,n){
if(i==n-1)cout<<ans[i]<<endl;
else cout<<ans[i]<<" ";
}
}
}
Recommended Posts