[PYTHON] Codeforces Round # 646 (Div. 2) Bacha Review (9/6)
This time's results
Impressions of this time
It's exactly the same impression as yesterday. I was able to solve the C problem with a light consideration, but I lost my concentration due to the ** E problem ** and was watching YouTube during the Bachacon. I don't think there is any other way than to step on it myself, so I'll do my best to make it work.
Also, although the E problem was too dusty and too particular about DP, it can be solved with a devised greedy method **, so I will be able to calmly identify it.
Problem A
I thought too much and issued 1WA. It is a reflection. I noticed that even and odd numbers can be adjusted by swapping even numbers and odd numbers in order to make the total odd numbers. Due to the condition that even numbers and odd numbers are exchanged, ** when only even numbers or only odd numbers ** cannot be exchanged, so it is necessary to separate cases. Furthermore, even when $ x = n $, all the elements are selected, so it is impossible to replace them. Therefore, it is sufficient to implement the following case classification.
(1) In case of even number only Since the sum of arbitrary elements is even, No is output. (2) For odd numbers only If the number of selected elements is odd, the sum is odd, so Yes is output. If the number of selected elements is even, the sum is even, so No is output. (3) When $ x = n $ If the sum of all elements is odd, Yes is output, and if it is even, No is output.
A.py
for _ in range(int(input())):
n,x=map(int,input().split())
a=list(map(int,input().split()))
l,r=sum(a[i]%2==1 for i in range(n)),sum(a[i]%2==0 for i in range(n))
if l==0:
print("No")
elif x==n:
print(["No","Yes"][sum(a)%2])
elif r==0:
print(["No","Yes"][x%2])
else:
print("Yes")
Problem B
Paraphrase the condition of a string that does not include $ 010 $ or $ 101 $ as a subsequence. This means that if a string starts with 1, for example, the next time 0 comes, 1 will not appear after that (even if it starts with 0).
Therefore, it can be said that the following character string is a character string that satisfies the subject.
0…01…1
1…10…0
Therefore, the original character string is changed to 0… 0, the required number of operations is calculated, and the difference is managed for the two patterns when 1 is increased from the left side and when 1 is increased from the right side from that state. However, you can calculate the required number of operations for each and find the minimum number of operations.
Also, regarding the difference, if $ s [i] = "0" $, the number of operations should be +1 and if $ s [i] = "1" $, the number of operations should be -1. * It took a long time to implement it because of the consideration. It is a reflection.
B.py
for _ in range(int(input())):
s=input()
n=len(s)
c0,c1=s.count("1"),s.count("1")
ans=min(c0,c1)
#0...Change from left when 0
for i in range(n):
if s[i]=="0":
c0+=1
else:
c0-=1
ans=min(ans,c0)
#From the right
for i in range(n-1,-1,-1):
if s[i]=="0":
c1+=1
else:
c1-=1
ans=min(ans,c1)
print(ans)
C problem
It's a simple problem if you see it as a gag. I want the ability to think about such issues in a stable manner.
Consider removing the order from one. At this time, ** when the order is 1 or less from the beginning for the given vertex $ x $ **, the first vertex Ayush can delete that vertex, so consider this case.
Therefore, for a given vertex $ x $, the order is greater than or equal to 2. Also, if the degree of $ x $ becomes 1, $ x $ will be selected by the other party, so ** avoid that state **. Furthermore, I noticed that the defeat is confirmed when the two vertices extend from the vertex $ x $ as shown in the figure below.
From the above, it can be said that when the order of the vertex $ x $ is 2 or more, ** by taking optimal actions with each other, the final shape is reached ** (** pay attention to the final state! * *)about it. Therefore, when the order of the vertex $ x $ is 2 or more, the victory or defeat depends only on the number of vertices $ n $, not the shape of the tree. Also, if three vertices remain in the end, you will lose, so if $ n $ is odd, you will lose the first Ayush, and if $ n $ is even, you will lose the second Ashish.
C.py
name=["Ayush","Ashish"]
for _ in range(int(input())):
n,x=map(int,input().split())
check=0
for i in range(n-1):
u,v=map(int,input().split())
if u==x or v==x:
check+=1
if check==0 or check==1:
print(name[0])
else:
print(name[n%2])
D problem
I haven't solved it because it's interactive.
E problem
It is a problem that can be solved if you concentrate as you can see in the impression. I don't think I can improve my mentality and concentration from my daily life, so I would like to improve it. Also, in this problem, I wrote it in PyPy using recursion and it was MLE, so when writing recursion in Codeforces, I would like to write it in C ++ **.
First, if ** $ b [i] = c [i] $, there is no need to change **, so shuffle in the subtree to replace the ones in $ b [i] \ neq c [i] $. I will do it. At this time, a type (type 0) in which $ b [i] = 0 $ and $ c [i] = 1 $ and a type (type 0) in which $ b [i] = 1 $ and $ c [i] = 0 $ There are two types of 1), ** if the sums of these are not equal **, the subject cannot be satisfied. Also, if they are equal to each other, the subject is always satisfied.
Based on this, ** the easiest thing to ask is to select a subtree that considers vertex 1 as the vertex. However, there are some cases where it is best to select a subtree that is closer to the leaves and shuffle it. ** Generalize the above, and if the cost of the parent of a vertex is smaller **, then the cost of that parent can be used as the cost of that vertex **. Therefore, it can be DFS (or BFS) and updated in order from the top vertices.
From the above, ** the cost of each vertex has been updated **, and the cost can be set so that it decreases monotonically from the root to the leaf **. Therefore, this source allows you to greedily ** shuffle from the leaves. In other words, assuming that the number of vertices of type $ i $ contained in the subtree is $ c \ _i $, the number of vertices that can be shuffled and matched is $ 2 \ times min (c \ _ 0, c \ _1) $. Do this in order from the apex closest to the leaf. Also, ** one of the types may not be matched by the subtree alone **, so shuffle the subtree with its parent as the root to match. Also, since it is performed in order from the vertex closest to the leaf, it is implemented by ** DFS ** here.
E.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 1000000000000000 //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
vector<ll> a,b,c;
vector<vector<ll>> tree;
vector<bool> check;
vector<ll> ans;
void dfs1(ll i,ll m){
FORA(j,tree[i]){
if(!check[j]){
check[j]=true;
a[j]=min(a[j],m);
dfs1(j,a[j]);
}
}
}
pair<ll,ll> dfs2(ll i){
ll ret=0;
pair<ll,ll> now={(b[i]==0 and c[i]==1),(b[i]==1 and c[i]==0)};
FORA(j,tree[i]){
if(!check[j]){
check[j]=true;
pair<ll,ll> d=dfs2(j);
ret+=ans[j];
now.F+=d.F;
now.S+=d.S;
}
}
ret+=(min(now.F,now.S)*a[i]*2);
ans[i]=ret;
return MP(now.F-min(now.F,now.S),now.S-min(now.F,now.S));
}
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
a=vector<ll>(n);b=vector<ll>(n);c=vector<ll>(n);
REP(i,n)cin>>a[i]>>b[i]>>c[i];
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);}
if(accumulate(ALL(b),0)!=accumulate(ALL(c),0)){cout<<-1<<endl;return 0;}
check=vector<bool>(n,false);check[0]=true;
dfs1(0,a[0]);
ans=vector<ll>(n,INF);
check=vector<bool>(n,false);check[0]=true;
dfs2(0);
cout<<ans[0]<<endl;
}
After the F problem
I will skip this time
Recommended Posts