[PYTHON] AtCoder Beginner Contest 155 Review
This time's results
Impressions of this time
(I was soaked in skis for three weeks and had no motivation for the competition professionals, but I would like to resume from today (2/26)) I couldn't solve up to C this time. When I saw the answer of D's assumed solution in a binary search, it was not difficult as an idea, so I felt the importance of devotion. Regarding E, we couldn't make a good distinction depending on whether or not to carry. I am very disappointed. I feel like I've said 200 million times that I want to think more organized.
Problem A
Except for the case where a, b and c are all the same and the case where a, b and c are all different.
A.py
a,b,c=map(int,input().split())
if (a==b and b==c) or (a!=b and b!=c and c!=a):
print("No")
else:
print("Yes")
B problem
Only when it is an even number, check whether it is a multiple of 3 or a multiple of 5, and if there is something that does not exist, break it.
B.py
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
if a[i]%2==0:
if a[i]%3==0 or a[i]%5==0:
continue
else:
print("DENIED")
break
else:
print("APPROVED")
C problem
I want to count how many each character string exists, so I manage it in a dictionary. After counting all the character strings in the dictionary, if you list the dictionary, you will have a list with the tuple of the "key / value pair" of the dictionary as an element. Since we want to find the maximum number of strings, we can sort by the second element of the tuple. Also, when outputting multiple character strings, they are output in alphabetical order, so sort by the first element of the tuple first. Implementing the above, it becomes as follows.
C.py
d=dict()
n=int(input())
for i in range(n):
s=input()
if s in d:
d[s]+=1
else:
d[s]=1
d=list(d.items())
d.sort(key=lambda x:x[0])
d.sort(key=lambda x:x[1],reverse=True)
m=len(d)
for i in range(m):
if d[i][1]==d[0][1]:
print(d[i][0])
else:
break
D problem
First of all, since k is 10 ^ 10 at the maximum, it can be seen that ** the method of checking from the front is definitely not in time **. Here, ** binary search ** can be used because the monotonicity and range of the number are fixed **.
Looking at the problem with the dichotomy in mind, we find the product, so the product of positive or negative numbers is positive, the product of positive and negative numbers is negative, at least one. You can see that if is 0, it becomes 0. Therefore, we considered each case separately.
First, if the kth number is negative, you can choose one from the set of positive numbers (b3) and one from the set of negative numbers (b1). Also, here, the product of the maximum number of absolute values is the minimum and -1 is the maximum, so the kth smallest number in that interval is searched by binary search. At this time, the countk1 function is used to count the number of numbers less than or equal to a certain number of t. The countk1 function counts how many numbers are less than or equal to the negative number x given a set of positive numbers and a set of negative numbers. Here, we will look at the elements of a set of negative numbers in order, and then find out how many positive numbers there are such that the product with those elements is x or less by binary search ($ O (n )). log n) $).
Next, if the kth number becomes 0, 0 is calculated as it is.
Finally, if the kth number is positive, you can choose two numbers from a set of positive numbers or a set of negative numbers, which is a bit more complicated. First, the minimum number can be 1, but the maximum number is the larger of the products of the two sets with the largest absolute values of each set, and the number of elements in either set is two. Note that there must be more than one. Under this, the k-th number (the case where it becomes negative and the case where it becomes 0 can be subtracted in advance) can be searched by a binary search in the same way as when the k-th number is negative. Here, the countk1 function Use the countk2 function to find it. As with the countk1 function, one can be fixed and a binary search can be performed, but a binary search must be performed for each of the negative number set and the positive set, within the same set. It should be noted that in order to select two numbers without duplication from, the index to be searched by the binary search must be i + 1 instead of 0.
If you divide the above cases and write the binary search code carefully, the code will be as follows. (It was difficult to implement ..., I feel like I've become a full-fledged person when I can write code like this quickly ...)
answerD.cc
#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<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
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#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 INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
ll l1,l2,l3;
ll countk1(ll x,vector<ll> b11,vector<ll> b13){
ll ret=0;
REP(i,l1){
#Binary search part(Does it satisfy x or less?)
ll lx=0;ll rx=l3-1;
while(lx+1<rx){
ll t=(lx+rx)/2;
if(b13[t]*b11[i]<=x){lx=t;}else{rx=t;}
}
#Be careful about how to write here
if(b13[rx]*b11[i]<=x){
ret+=(rx+1);
}else if(b13[lx]*b11[i]<=x){
ret+=(lx+1);
}
}
return ret;
}
ll countk2(ll x,vector<ll> b21,vector<ll> b23){
ll ret=0;
REP(i,l1-1){
#The beginning of the binary search is i instead of 0+1(Do not allow duplication)
ll lx=i+1;ll rx=l1-1;
while(lx+1<rx){
ll t=(lx+rx)/2;
if(b21[t]*b21[i]<=x){lx=t;}else{rx=t;}
}
if(b21[rx]*b21[i]<=x){
ret+=(rx-i);
}else if(b21[lx]*b21[i]<=x){
ret+=(lx-i);
}
}
REP(i,l3-1){
#The beginning of the binary search is i instead of 0+1(Do not allow duplication)
ll lx=i+1;ll rx=l3-1;
while(lx+1<rx){
ll t=(lx+rx)/2;
if(b23[t]*b23[i]<=x){lx=t;}else{rx=t;}
}
if(b23[rx]*b23[i]<=x){
ret+=(rx-i);
}else if(b23[lx]*b23[i]<=x){
ret+=(lx-i);
}
}
return ret;
}
signed main(){
ll n,k;cin >> n >> k;
vector<ll> b1,b2,b3;
REP(i,n){
ll x;cin >> x;
if(x<0){b1.PB(x);}else if(x==0){b2.PB(x);}else{b3.PB(x);}
}
l1=b1.size();l2=b2.size();l3=b3.size();
sort(ALL(b1));sort(ALL(b3),greater<ll>());
if(k<=l1*l3){
ll l=b1[0]*b3[0];ll r=-1;
while(l+1<r){
ll t=(l+r)/2;
if(countk1(t,b1,b3)>=k){r=t;}else{l=t;}
}
if(countk1(l,b1,b3)==k){
cout << l << endl;
}else{
cout << r << endl;
}
}else if(k<=l1*l3+l2*(l1+l3)+(l2*(l2-1))/2){
cout << 0 << endl;
}else{
k-=(l1*l3+l2*(l1+l3)+(l2*(l2-1))/2);
ll l=1;ll r;
if(l1>=2 and l3<2){
r=b1[0]*b1[1];
}else if(l1<2 and l3>=2){
r=b3[0]*b3[1];
}else{
r=max(b1[0]*b1[1],b3[0]*b3[1]);
}
sort(ALL(b3));sort(ALL(b1),greater<ll>());
while(l+1<r){
ll t=(l+r)/2;
if(countk2(t,b1,b3)>=k){r=t;}else{l=t;}
}
if(countk2(l,b1,b3)==k){
cout << l << endl;
}else{
cout << r << endl;
}
}
}
E problem
After a few experiments, it's easy to see that due to the influence of other digits ** I can't decide on greed ** (I'm greedy as soon as I leave the competition pro. It's not good.) I will. Experiments also show that there are $ 2 $ ways to pay more or just when paying attention to a certain digit. (It's easy to understand if you think about n = 1 ~ 9.) In other words, if you pay 1 more for each digit (to pay more for the digits below it) and if you just pay ** $ 2 $ If you prepare an array for DP that holds the state of **, you can find it by deciding in order from the upper digit. DP tends to work well with this generalization, so I'd like to do my best to be able to think ** generalize without rushing ** during the contest.
answerE.py
n=[int(x) for x in list(input())]
k=len(n)
dp=[[-1,-1] for _ in range(k)]
dp[0]=[min(1+(10-n[0]),n[0]),min(1+(10-n[0]-1),n[0]+1)]
for i in range(1,k):
dp[i]=[min(dp[i-1][1]+(10-n[i]),dp[i-1][0]+n[i]),min(dp[i-1][1]+(10-n[i]-1),dp[i-1][0]+n[i]+1)]
print(dp[k-1][0])
F problem
I don't think it's suitable for the level yet, so I'll skip it this time.
Recommended Posts