Codeforces Round # 643 (Div. 2) Review
This time's results
Impressions of this time
I started AtCoder about a year ago, but I decided to appear in Kodofo, who heard that there are many contests. I'm not going to do it for the time being because there are too many problems to fill in the past questions, but I will come out every time when the time is not too late. This is the second time, and I'm not used to the Kodofo format and problem sentences in English, but I think I'm getting good grades. In addition, ABC basically provides all-question explanation AC, but Kodofo will try to explain lightly only the problems that can be solved and the problems that are likely to be solved soon.
Problem A
When I first saw it ** I was impatient because I couldn't grasp the law at all **.
However, if even one 0 is mixed in the digit when converted to a decimal number, $ minDigit (a_n) = 0 $, and $ k \ geqq n $ does not change the value of $ a_k $. .. Also, it is predicted that $ minDigit (a_n) = 0 $ will be reached soon ($ \ because $ is unlikely to be $ minDigit (a_n) \ neq0 $ at any n), so $ minDigit (a_n) = 0 When it became $, $ a_k $ at that time was output and broken.
Since it is a problem of competitive programming, there are a certain number of problems that can be solved without strict proof, so I would like to solve it. (Although it should be proved in my head)
A.py
t=int(input())
for i in range(t):
a,k=map(int,input().split())
for i in range(k-1):
ax=str(a)
l,r=int(min(ax)),int(max(ax))
if l==0:
print(a)
break
else:
a+=(l*r)
else:
print(a)
Problem B
I misunderstood that I had to include everyone in the group ... Since it is not necessary to include everyone in the group, select the people with the smallest "number of people required for the group" in order. At this time, the number of people selected as a group must be equal to or greater than the "required number of people in the group" of each person, so if it is not more than the "required number of people in the group", add as many people to the group as necessary. To do. And if the group meets the conditions, it can be added to the number of groups of the subject. In Python, I passed the pretest, so I was careful, but it became TLE. For such a marginal amount of calculation, it may be more reliable to throw C ++.
B.py
t=int(input())
for i in range(t):
n=int(input())
e=sorted(list(map(int,input().split())))
ans,now=0,0
while True:
nowx=now+e[now]
while nowx<n:
if nowx-now<e[nowx-1]:
nowx=now+e[nowx-1]
else:
break
if nowx>=n:
if nowx==n:
if nowx-now>=e[nowx-1]:
ans+=1
break
else:
ans+=1
now=nowx
print(ans)
answerB.cc
//Include(Alphabetical order)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
//for loop relationship
//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.
#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--)
//x is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
#define MAX(x) *max_element(ALL(x)) //Find the maximum value
#define MIN(x) *min_element(ALL(x)) //Find the minimum value
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
signed main(){
ll t;cin >> t;
vector<ll> answers(t);
REP(i,t){
ll n;cin >> n;
vector<ll> e(n);REP(j,n)cin >> e[j];
sort(ALL(e));
ll ans=0;ll now=0;
while(true){
ll nowx=now+e[now];
while(nowx<n){
if(nowx-now<e[nowx-1]){
nowx=now+e[nowx-1];
}else{
break;
}
}
if(nowx>=n){
if(nowx==n){
if(nowx-now>=e[nowx-1]){
ans++;
}
}
break;
}else{
ans++;
now=nowx;
}
}
answers[i]=ans;
}
REP(i,t){
cout << answers[i] << endl;
}
}
C problem
I'm glad that I was able to think about this issue properly. First, in order to hold as a triangle, (sum of the smallest two sides)> (maximum one side) must hold.
Also, $ A \ leqq x \ leqq B \ leqq y \ leqq C \ leqq z \ leqq D $ holds between the three sides of the triangle $ x, y, z $, so $ x + y> z $ All you need is. Furthermore, $ A + B \ leqq x + y \ leqq B + C $ holds, and it is clear that this x + y candidate is on the order of about $ 10 ^ 5 $, so it is the original that x + y is decided. I thought that I should find the candidate for z by $ O (1) $ (** It is natural to think that I want to fix one because there are three unknowns **, if x is fixed, if z is fixed As a result of conducting experiments such as, we came to the result that it is better to fix with x + y.).
If you think so far, you can find out how many z are smaller than x + y, but there is one pitfall here. Candidates for the value of x + y are on the order of about $ 10 ^ 5 $, but there are multiple pairs of x and y for the value of x + y. The processing of these multiple things can be thought of well by drawing the figure below. (I'm glad I was able to calm down this consideration. I had a similar problem with AtCoder before and couldn't solve it ...)
Therefore, the candidates for the (x, y) pair when $ x + y = k $ can be found, and the candidate for z at this time is as shown in the image below.
Therefore, the answer is the product of the number of pairs of (x, y) when $ x + y = k $ and the number of candidates for z.
C.py
a,b,c,d=map(int,input().split())
xy=dict()
for i in range(a+b,b+c+1):
f=min(i-a-b+1,b+c-i+1)
f=min(f,b-a+1,c-b+1)
xy[i]=f
ans=0
for i in range(a+b,b+c+1):
if i>d:
ans+=(xy[i]*(d-c+1))
elif i<=c:
continue
else:
ans+=(xy[i]*(i-c))
print(ans)
D problem
I'm not sure about the proof because I've blown away the thought process and solved the problem.
However, Petya can ** create an array conveniently **, which leads to the idea that Petya wants to ** create a convenient array in order to win. Also, as long as there is no such thing as a sum of k or Sk for the subarray, if you pay attention to its symmetry, ** the subarray whose sum is close to 0 and the sum is close to S I thought it would be good to assume an array ** in which only a partial array exists.
Such an array would look like the figure below (n is case), noting that all elements of the array are greater than or equal to 1 and less than or equal to S-1 and the sum of all elements is S. Don't worry about it being closed.)
Assuming an array like the one shown above, the sum of the subarrays can be $ 1 $ ~ $ n-1, S- (n-1) $ ~ $ S $, and ** symmetry can also be considered. I thought it would be convenient because it is **. Also, in order to make this convenient array (Petya wins), it is sufficient if there is a k that satisfies $ n-1 <k <S- (n-1) $, and there is such a k. The condition for is $ n-1 <S- (n-1) $, and when implemented, it becomes as follows (when $ \ because $ k satisfies this, it is clear that Sk also satisfies this. ).
answerD.py
n,s=map(int,input().split())
if n<s-(n-1):
print("YES")
print(" ".join(map(str,[1 if i!=n-1 else s-(n-1) for i in range(n)])))
print(n)
else:
print("NO")
E Problem
I've seen some solutions to the ternary search, but I haven't done the ternary search yet, so I'll skip it this time.
F problem
As with the E problem, I think I'm still lacking in ability, so I'll skip this time.
Recommended Posts