AtCoder Beginner Contest 155 Review

This time's results

スクリーンショット 2020-02-17 19.39.14.png

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

AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Beginner Contest 177
AtCoder Beginner Contest 172
AtCoder Beginner Contest 173
AtCoder Beginner Contest 066 Review past questions
AtCoder Beginner Contest 181 Note
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 182 Note
AtCoder Grand Contest 048 Review
AtCoder Beginner Contest 156 WriteUp
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
Solve AtCoder Beginner Contest 100-102
AtCoder Beginner Contest 167 Memorandum
AtCoder Beginner Contest 183 Note
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 184 Note
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 188 Note
AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 105 Review of past questions