[PYTHON] Codeforces Round # 665 (Div. 2) Bacha Review (8/23)
This time's results
Impressions of this time
Although I made a mistake, I was able to pass through the C problem at a reasonable speed, but I solved it with ** half give up ** for the D problem. As a result, I was able to pass after the contest, so I regret it. As I mentioned in the previous article, I think that the grades will improve when the problems that can be solved soon become stable, so I will do my best. I think that it will change if I solve about 100 questions, so I will put up with it for about a month ** and try to bacha every day.
Problem A
I misread the problem statement, but I am glad that I was able to recover.
First of all, it is illustrated to understand the positional relationship between ** A and B **. There are the following two patterns.
When ** $ n <k $ **, the pattern ② requires the coordinates of $ A $ to be $ k $ or more, so the number of steps is at least $ k-n $. Also, in pattern (1), the coordinates of $ A $ are $ k $, so the number of steps required is $ k-n $. Therefore, the minimum number of steps required at this time is $ k-n $.
A.py
for _ in range(int(input())):
n,k=map(int,input().split())
if n==k:
print(0)
elif n>k:
if (n+k)%2==0:
print(0)
else:
print(1)
else:
print(k-n)
Problem B
You should think about the optimal combination in order. Since there are only three types of $ a \ _i $, consider the optimal combination for each value.
(1) When $ a \ _i = 2 $
** $ c \ _i $ takes a maximum value of 2 by combining it with $ b \ _i = 1 $ **. Combine as many as you can, but if you have a surplus ($ z \ _1> y \ _2 $) ** the rest can be combined with $ b \ _i = 2 $ **. This is because $ a \ _i = 1 $ has a negative effect on the total value when combined with $ b \ _i = 2
(2) When $ a \ _i = 1 $ Since $ c \ _i $ is not positive, it should be ** paired with $ b \ _i \ neq 2 $ so that it is not negative **. In other words, if it can be paired with $ x \ _2 + y \ _2 $ other than the combination in (1), the amount of change will be 0. Also, if there is a surplus ($ y \ _1> x \ _2 + y \ _2 $) even if paired with these, it is sufficient to subtract $ \ times 2 $ (the number of pairs) as it has a negative effect.
(3) When $ a \ _i = 0 $ The result is 0 when combined with any $ b \ _i $, so the total value is not affected and can be ignored.
If you implement the above carefully with the corner case, it will be as follows. Also, be careful not to make a mistake in the order of subtraction **.
B.py
for _ in range(int(input())):
x1,y1,z1=map(int,input().split())
x2,y2,z2=map(int,input().split())
ans=0
#First from z1
if z1<=y2:
ans+=(2*z1)
y2-=z1
z1=0
else:
ans+=(2*y2)
z1-=y2
y2=0
if z1<=z2:
z2-=z1
z1=0
else:
z1-=z2
z2=0
x2-=z1
#Next is y1(x1 doesn't matter, it's zero anyway)
if y1<=x2+y2:
print(ans)
else:
print(ans-(y1-x2-y2)*2)
C problem
(My thoughts during the contest were fairly appropriate and close to lying. ** Thoughts with low reproducibility and accuracy **, so I'll write an improved one.)
First, consider whether it is possible to change elements that are in different positions to the correct position compared to the sorted array. At this time, if you pay attention to the elements with different positions and some of them are not multiples of ** $ a \ _ {min} $ **, gcd is $ a \ _ between this element and other elements. It can never be {min} $. Therefore, if there is something that is not a multiple of $ a \ _ {min} $, you can output "NO".
Next, consider the case where all the elements in different positions are multiples of $ a \ _ {min} $. At this time, all elements can be moved to the correct position by going through ** $ a \ _ {min} $ **. That is, suppose $ a \ _ {min} $ is in $ i $ and you want to move $ a \ _j $ to $ k $. At this time, ① select $ a \ _ {min} $ and $ a \ _ k $ and swap ② $ a \ _ k (= a \ _ {min}) $ and $ a \ _ j $ to swap And gcd can be moved as $ a \ _ {min} $. Therefore, it is possible to move a different element at any position to the correct position by moving it via $ a \ _ {min} $.
C.py
from math import gcd
def gcditer(x):
ret=x[0]
for i in range(1,len(x)):
ret=gcd(ret,x[i])
return ret
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
b=sorted(a)
#You should use the same one
#You can use it if it is a divisor
m=min(a)
c=[a[i] for i in range(n) if a[i]!=b[i] or a[i]%m==0]
if len(c)==0:
print("YES")
elif gcditer(c)==m:
print("YES")
else:
print("NO")
D problem
It's a similar problem, but I wasn't used to setting this problem **, so I spent too much time. As a result, I came up with the correct solution, but ** I didn't have enough time to notice the index error **.
First, consider $ \ sum_ {i = 1} ^ {n-1} \ sum_ {j = i + 1} ^ {n} f (i, j) $, but think honestly like this ** For a difficult sum **, it is better to ** consider the contribution of each element **. In other words, you should consider how many times each edge is included as a simple path (open path) between arbitrary vertices (✳︎) and multiply the path value.
Here, it is optimal to assume that ** (✳︎) is found on any side ** and ** to increase the number of sides that appear more often **. Also, since ** the number of 1s appearing on the edge must be as small as possible **, the cases can be classified as follows.
① When $ m <n-1 $ When the sides are arranged in descending order of the number of appearances, $ p $ should also be arranged in descending order and combined. At this time, since there is no $ p $ corresponding to $ n-1-m $ edges that appear less frequently, 1 is combined.
② When $ m \ geqq n-1 $ When the sides are arranged in descending order of the number of appearances, if $ p $ is arranged in descending order and combined, only $ m-n + 1 $ of $ p $ is left, so the side with the largest number of appearances is larger than $ p $ Combine it with the product of $ m-n + 2 $. Also, for the remaining edges, combine the remaining $ n-2 $ pieces of $ p $ in descending order.
Based on this, consider (✳︎). Therefore, I decided to ** pay attention to one side ** as shown in the figure below.
Then, by selecting the start point and end point of the simple path from each of the above ** circles **, you can create a simple path that includes that side. Also, if you pay attention to the lower circle here, you can see that it ** constitutes a subtree **. In other words, it is only necessary to know the number of vertices of the subtree, which can be calculated by DFS ** because it can be counted from the direction of the leaves. The number of vertices in the upper circle can be calculated by (total number of vertices)-(number of vertices in the lower circle). The lower circle is the subtree that does not contain the root $ \ leftrightarrow $ The subtree whose root is the vertex far from the root $ \ leftrightarrow $ ** The number of vertices included in the subtree out of the two vertices It can be rephrased as the subtree ** with less.
Therefore, (1) find the number of vertices of the subtree rooted at each vertex by DFS, (2) find how many times each edge is included using (1), and (3) sort and give the edges in descending order of the number of times they are included. The $ p $ that was created is also sorted in descending order, and ④ find the maximum value by combining edges and numbers (remember that it is $ mod \ 10 ^ 9 + 7 $). It will be like.
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,m;
vector<vector<ll>> edges;
vector<ll> dpc;
vector<vector<ll>> tree;
vector<ll> p;
vector<bool> check;
//Number of vertices of subtree
ll dfs(ll i){
//cout<<1<<endl;
ll ret=1;
check[i]=true;
FORA(j,tree[i]){
if(!check[j]){
ret+=dfs(j);
}
}
dpc[i]=ret;
return ret;
}
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
//Overflow anyway
ll t;cin>>t;
REP(_,t){
cin>>n;
dpc=vector<ll>(n,0);
tree=vector<vector<ll>>(n);
edges=vector<vector<ll>>(n-1);
check=vector<bool>(n,false);
REP(i,n-1){
ll u,v;cin>>u>>v;u--;v--;
tree[u].PB(v);
tree[v].PB(u);
edges[i]={u,v};
}
dfs(0);
vector<ll> dp(n-1,0);
REP(i,n-1){
ll l,r;l=edges[i][0];r=edges[i][1];
dp[i]=min(dpc[l],dpc[r])*(n-min(dpc[l],dpc[r]));
}
//FORA(i,dpc)cout<<i<<" ";
sort(ALL(dp),greater<ll>());
//Calculation process
cin>>m;
p=vector<ll>(m);
REP(i,m){
cin>>p[i];
}
sort(ALL(p),greater<ll>());
vector<ll> calc(n-1,1);
if(m<n-1){
REP(i,m){
calc[i]=p[i];
}
}else{
//Maybe this side is different
//I'll fix it later
REP(i,m-n+2){
calc[0]*=p[i];
calc[0]%=MOD;
}
FOR(i,m-n+2,m-1){
calc[i-m+n-1]=p[i];
}
}
ll ans=0;
REP(i,n-1){
ans+=(calc[i]*dp[i]);
ans%=MOD;
}
cout<<ans<<endl;
}
}
After the E problem
I will skip this time
Recommended Posts