Codeforces Round # 668 (Div. 2) Bacha Review (9/7)
This time's results
Impressions of this time
This time, I think I was facing the virtual console with a good concentration. However, the D problem asked me what I didn't have, but I regret it because it was ** knowledge I should know **. It's also a problem that you would have known if you were searching during the Virtual Console, so sometimes it may be good to use the search.
Problem A
It was a gag. If you don't notice it, you'll go crazy. ** It is good to think as ** $ p \ _1, p \ _2,…, p \ _n $ without experimenting strangely.
$ p \ _1 + p \ _2, p \ _2 + p \ _3,…, p \ _ {n-1} + p \ _n $, so if you reverse it, $ p \ _n + p \ _ {n-1 },…, p \ _3 + p \ _2, p \ _2 + p \ _1 $, and the numbers that appear are exactly the same.
Therefore, you can output the ones in reverse order.
A.py
for _ in range(int(input())):
n=int(input())
p=list(map(int,input().split()))
print(" ".join(map(str,p[::-1])))
Problem B
When the amount of calculation came out to the limit, I was impatient without passing, but it was good to be able to recover.
Consider selecting $ i, j $ and changing it to $ a \ _i-1, a \ _j + 1 $. At this time, if $ i \ <j $, no coins are needed, if $ i > j $, one coin is needed, and consider the minimum number of coins required to make everything 0. I will.
In the experiment with the sample, if you select $ i, j $ where ** $ a \ _i> 0, a \ _j <0 $, you can make a change ** that approaches 0 without using coins. I will. Also, by making this change,-and + on the right side will eventually remain on the left side, and at this time there is no choice but to perform operations using coins. For example, in the first sample, by performing an operation that does not use coins from -3 2 -3 4 to-3 0 -1 4and using 4 coins from that state, all elements are 0. Can be
Also, for the first coin-free operation, look at the elements that satisfy $ a [i]> 0 $ in order from the smallest $ i $, and use $ j (> i) $ that satisfies $ a [j] <0 $. It can be done by the greedy method of operating from the smallest $ j $ (the image is that $ \ because $ ** has fewer choices **!). Also, I tried to manage a small $ j $ with a set structure with $ j (> i) $ that satisfies $ a [j] <0 $, but in this case it takes logarithmic hours to insert, delete, and refer to the set. It will be TLE.
Here, $ j $ is the smallest index that satisfies $ i <j, a [j] <0 $, and when $ i $ is incremented by 1, $ j $ increases monotonically **. So, just have $ j $ in the index alone and think of an implementation like ** scale method **. Therefore, it can be implemented with the computational complexity of $ O (N) $.
B.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
for j in range(n):
if a[j]<0:
break
for i in range(n):
if a[i]>0:
j=max(i+1,j)
while True:
if j==n:
break
if a[j]<0:
m=min(a[i],-a[j])
a[i]-=m
a[j]+=m
if a[i]==0:
break
j+=1
if j==n:
break
ans=0
#print(a)
for i in range(n):
if a[i]>0:
ans+=a[i]
print(ans)
C problem
Note that the subsequence is ** continuous **. I was sharp without noticing it.
It is a continuous subsequence of $ k $ in length, and I want to see the difference **, so I wrote the figure below.
Then I noticed that the elements with indexes $ 0 $ and $ k $ are equal. Also, if this is generalized, the elements of the indexes $ i $ and $ i + k $ are equal, so if the remainders of the indexes divided by $ k $ are equal, then those elements are equal . I will. Therefore, first check if the elements are equal ( 0 and 1 are not included at the same time **) by dividing each index remainder. If there are unequal items at this point, NO is output.
Also, it is ** necessary condition ** that all elements are equal for each remainder index, and the number of 0s and 1s appearing in the continuous part of length $ k $ as ** sufficient condition ** must be equal. Must be. Therefore, find the element when the remainder is $ l $ for any $ l $. Also note that not only $ 0 $ and $ 1 $ but also **? **? The number of 0s is $ ans0 $, the number of 1s is $ ans1 $, and the number of? Is $ ex $. I will.
Consider the conditions sufficiently under this, but when $ ex = 0 $, if $ ans0 = ans1 $, the condition is satisfied, so YES is output, otherwise NO is output. Next, when $ ex \ neq 0 $, you can adjust by the number of?, So $ ans0 + ex \ geq [\ frac {k} {2}] $ and $ ans1 + ex \ geq [\ frac {k } {2}] If it is $, the condition is satisfied, so YES is output. If not, NO is output.
C.py
for _ in range(int(input())):
n,k=map(int,input().split())
s=input()
t=[[] for i in range(k)]
for i in range(n):
t[i%k].append(s[i])
#If there is something different, no at that point
ans0,ans1=0,0
ex=0
for i in range(k):
if t[i].count("0")>0 and t[i].count("1")>0:
print("NO")
break
elif t[i].count("0")>0:
ans0+=1
elif t[i].count("1")>0:
ans1+=1
else:
ex+=1
else:
if ex==0:
if ans0==ans1:
print("YES")
else:
print("NO")
else:
if ans0+ex>=k//2 and ans1+ex>=k//2:
print("YES")
else:
print("NO")
D problem
In the following, Alice will be abbreviated as A and Bob as B. Also, let A be the distance traveled once by $ da $, and the distance traveled by B once be $ db $.
B runs away from A. Since A is the first player, ** if you can reach B the first time, A wins **. Therefore, consider ** the optimal movement for each ** while A cannot reach B the first time. First, consider the optimal movement of B. ** B doesn't have to move until A gets close to the limit **. When A gets close to the limit, if there is a vertex in the direction away from A, it is better to move there, but if there is no such vertex, it is necessary to move across A to a distant vertex. On the other hand, the optimal movement of A is not to move as close to B as possible, but to move ** to a distance of $ da $. The reason is that if it gets closer than that, it will be easier for B to escape when it straddles A and escapes.
From the above considerations, it is thought that A is caught in $ db \ leqq 2 \ times da $ and B is kept escaping in $ db> 2 \ times da $. However, ** B may not be able to escape this far **. Because $ db $ can be up to $ n-1 $, but the distance between vertices on the tree can be less than $ n-1 $ (e.g. star graph). That is, $ db $ must be ** replaced ** with $ min (db, $ the maximum distance between two vertices on the tree). Here, I did not know how to find the maximum distance between two vertices on the tree ** in the virtual console, but when I investigated it, it seems that the ** tree diameter ** corresponds to this. Therefore, $ db = min (db, $ tree diameter) should be set.
The diameter of the tree can be calculated by following the algorithm below by referring to this article.
I won't make it into a library because it's easy to do BFS (or DFS) twice, but I'd like to be able to solve it in the future. Also, as for the proof, a simple one is written in the previous article.
Therefore, from the above, it was possible to determine which of A and B wins in any case.
D.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
ll n,a,b,da,db;
vector<vector<ll>> tree;
vector<ll> check;
vector<ll> check2;
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(_,t){
cin>>n>>a>>b>>da>>db;
tree=vector<vector<ll>>(n);
REP(i,n-1){
ll u,v;cin>>u>>v;
tree[u-1].PB(v-1);
tree[v-1].PB(u-1);
}
check=vector<ll>(n,INF);
deque<ll> d={a-1};
ll dep=0;
while(SIZE(d)){
ll l=SIZE(d);
REP(i,l){
ll now=d.front();
check[now]=dep;
FORA(j,tree[now]){
if(check[j]==INF)d.PB(j);
}
d.pop_front();
}
dep++;
}
check2=vector<ll>(n,INF);
d={ll(distance(check.begin(),max_element(ALL(check))))};
dep=0;
while(SIZE(d)){
ll l=SIZE(d);
REP(i,l){
ll now=d.front();
check2[now]=dep;
FORA(j,tree[now]){
if(check2[j]==INF)d.PB(j);
}
d.pop_front();
}
dep++;
}
//cout<<check[b-1]<<" "<<da<<endl;
if(check[b-1]<=da){
cout<<"Alice"<<endl;
//cout<<1<<endl;
continue;
}
if(min(db,*max_element(ALL(check2)))<=2*da){
cout<<"Alice"<<endl;
}else{
cout<<"Bob"<<endl;
}
}
}
After the E problem
I will skip this time
Recommended Posts