[PYTHON] Codeforces Round # 592 (Div. 2) Bacha Review (11/03)
This time's results
Impressions of this time
I made a mistake in high school math because of the C problem. Partly because I used the library for the second time, I'm disappointed that I couldn't debug it during the contest.
Moreover, the D problem was so easy that I was even more disappointed ... I'd like to feed on my regrets, but it's difficult to deal with bugs.
Problem A
This is easy. All you have to do is prepare enough pens and pencils for lecture and practical class. In other words, you only need $-(-a // c) and-(-b // d) $ books, respectively.
A.py
for _ in range(int(input())):
a,b,c,d,k=map(int,input().split())
x=-(-a//c)
y=-(-b//d)
if x+y>k:
print(-1)
else:
print(x,y)
Problem B
I feel that it is a problem that requires esper power. If you experiment with ** samples **, you will find that ** all rooms can be traced if the end rooms are connected on the upper and lower floors **. Therefore, if this is applied to other cases, it is best to move to another floor in the room closest to the edge ** or to follow only the room on that floor while the upper and lower floors are connected. is. You can see it by looking at the figure below.
Therefore, you can write the following code considering the three patterns of moving to another floor starting from the left and right ends and tracing only the room on one floor.
B.py
for _ in range(int(input())):
n=int(input())
s=list(map(int,input()))
ans=n
if 1 not in s:
print(ans)
continue
for i in range(n):
if s[i]==1:
ans=max(ans,n*2-i*2)
break
for i in range(n-1,-1,-1):
if s[i]==1:
ans=max(ans,n*2-(n-1-i)*2)
break
print(ans)
C problem
There was a problem ** such as having to use a 128-bit integer **, so I was impatient and could not debug. In this problem, $ w, d, p, n $ is given to determine if there is a non-negative integer $ x, y, z $ that satisfies the following, and if so, the appropriate set is selected. Just ask.
First, there are only two equations for the three variables $ x, y, z $, so ** the answer is not uniquely determined **. Here, $ z $ appears only in ②, so consider deciding $ x, y $ first. That is, if you look at equation (1), you can see that it is a two-dimensional, first-order indefinite equation, so solve this to find a set of $ x, y $ that makes $ x + y $ as small as possible, and that $ x, y $ is $. If x + y \ leqq n $ is satisfied, $ z $ also exists.
Now that $ d \ <w $, you should aim to make $ x $ as large as possible ($ \ leftrightarrow $ ** $ y $ as small as possible **). Also, if you use the Library of binary linear indefinite equations created yesterday, $ x = x \ _ 0 + m * b, y = y \ _0- You can find $ x \ _0, y \ _0, a, b $ which is m * a $. Therefore, when $ y \ _0 $ is positive, $ m = floor (y \ _ 0, a) $, and when $ y \ _0 $ is negative, $ m = ceil (-y \ _ 0, a) $. Then, $ y $ becomes the minimum, so $ x, y $ obtained for this $ m $ is a set of $ x, y $ that minimizes $ x + y $, and this satisfies the above condition. Just think about it.
C_overflow.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
//Return value:Greatest common divisor of a and b
// ax + by = gcd(a, b)Meet(x, y)Is stored
ll extGCD(ll a, ll b, ll &x, ll &y) {
if(b==0){
x=1;
y=0;
return a;
}
ll d=extGCD(b,a%b,y,x);
y-=a/b*x;
return d;
}
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 n,p,w,d;cin>>n>>p>>w>>d;
if(p%gcd(w,d)!=0){
cout<<-1<<endl;
return 0;
}
ll f=gcd(w,d);
ll h=p/f;
ll x,y;
extGCD(w,d,x,y);
//At this point y should be as small as possible(x is large)
x*=h;y*=h;
// /cout<<x<<" "<<y<<endl;
w/=f;
d/=f;
if(y>=0){
ll g=y/w;
x+=g*d;
y-=g*w;
}else{
ll g=(-y+(w-1))/w;
x-=g*d;
y+=g*w;
}
//cout<<x<<" "<<y<<endl;
if(x<0 or x+y>n){
cout<<-1<<endl;
}else{
//cout<<x<<endl;
//cout<<(n-x-y)<<endl;
cout<<x<<" "<<y<<" "<<(n-x-y)<<endl;
}
}
C.py
from sys import setrecursionlimit
setrecursionlimit(10**8)
def extgcd(a,b,x,y):
if b==0:
x[0]=1
y[0]=0
return a
e=extgcd(b,a%b,y,x)
y[0]-=(a//b)*x[0]
return e
n,p,w,d=map(int,input().split())
from math import gcd
if p%gcd(w,d)!=0:
print(-1)
exit()
f=gcd(w,d)
h=p//f
x,y=[0],[0]
extgcd(w,d,x,y)
x=x[0]*h
y=y[0]*h
w//=f
d//=f
if y>=0:
g=y//w
x+=g*d
y-=g*w
else:
g=-(y//w)
x-=g*d
y+=g*w
if x<0 or x+y>n:
print(-1)
else:
print(x,y,n-x-y)
D problem
It was 2000 times easier than the C problem when I solved it after the contest. What?
When I first read it, I thought it was a tree DP, but I don't have to do that much. First, the condition that the vertices contained in the path represented by three different vertices are painted in different colors must be ** no vertices of degree 3 or higher **. This can be shown by reductio ad absurdum.
At this time, there is only ** path graph ** as a concatenated graph in which the degree of any vertex is 2 or less and does not include a cycle. You can easily understand it by extending the sides in order from the apex of the end (of order 1). Therefore, it first determines whether it will be a path graph, and if it is not a path graph, it immediately outputs -1. On the other hand, when it comes to a path graph, it is easy to show that ** there is a color painting method that always satisfies the conditions **. In other words, when you paint the color $ a, b, c $ from the edge, the remaining vertices are uniquely painted as $ a, b, c, a, b, c,… $. Therefore, it is only necessary to find the cost for each of the three vertices of the path graph (3! Ways) and find the minimum value **. In addition, 3! Streets can be written out with the permutation function, and in each case it is only necessary to perform calculations up to $ 10 ^ 5 $ times, so it operates sufficiently fast. You can reduce the constant multiple by the cumulative sum, but it is not necessary because there is a margin in the amount of calculation.
D.py
n=int(input())
c=[list(map(int,input().split())) for i in range(3)]
edges=[[] for i in range(n)]
for i in range(n-1):
u,v=map(int,input().split())
edges[u-1].append(v-1)
edges[v-1].append(u-1)
for i in range(n):
if len(edges[i])>2:
print(-1)
exit()
path=[]
for i in range(n):
if len(edges[i])==1:
path.append(i)
break
#print(path)
#print(edges)
seen=[False]*n
seen[path[-1]]=True
#exit()
while True:
for i in edges[path[-1]]:
if not seen[i]:
path.append(i)
seen[i]=True
break
else:
break
#print(path)
d=[[0]*n for i in range(3)]
for i in range(3):
now=0
for j in path:
d[i][now]=c[i][j]
now+=1
#print(d)
from itertools import permutations
ans=10**30
now=[]
for i in permutations(range(3),3):
ans_sub=0
now_sub=[0]*n
for j in range(n):
now_sub[path[j]]=i[j%3]+1
ans_sub+=d[i[j%3]][j]
if ans_sub<ans:
ans=ans_sub
now=now_sub
print(ans)
print(" ".join(map(str,now)))
After the E problem
I will not solve this time.
Recommended Posts