AtCoder Beginner Contest 114 Review of past questions

Time required

スクリーンショット 2020-04-18 9.58.07.png

Impressions

After I came up with a solution, I tried to do it without organizing it, so it took a long time to implement extra to solve the D problem. I want to keep in mind ** implementation after I finish organizing and see the path **.

Problem A

Outputs YES if the input is 3, 5 or 7.

answerA.py


x=int(input())
print("YES" if x==3 or x==5 or x==7 else "NO")

B problem

The character string S is examined in order from the front, and the smallest absolute value of the difference from 753 is output.

answerB.py


s=input()
l=len(s)
ans=[]
for i in range(l-3+1):
    ans.append(abs(int(s[i:i+3])-753))
print(min(ans))

C problem

In such a problem, ** counting using a recursive function ** and O (the number of 753 numbers). However, I wanted to do it in a different way to skip the implementation of the recursive function, so I thought of a different way to count all the possible numbers and find it in a binary search. Specifically, the 753 number is `[" 3 "," 5 "," 7 "]`, which is the direct product of the ** array ** (** the product function of itertools is convenient **, so please remember it. Let's keep it in mind.) Of the numbers combined as a character string without changing the order, 3 and 5 and 7 appear at least once, so I put all such numbers in the ans array. Then, I sorted the ans array in ascending order and searched for how many elements ** n or less by binary search **. (The last part of the output is wasteful because I had a bug in my head. If I fix the waste, it will look like a comment out.) Also, it is okay to avoid recursive functions, but without a binary search **, when searching for the first 753 number candidates, just count whether it is n or less and the answer can be obtained immediately **. I noticed. The improved version is the third code.

answerC.py


from itertools import product
n=int(input())
ans=[]
for i in range(3,10):
    l=list(product(["3","5","7"],repeat=i))
    for j in l:
        if len(set(j))==3:
            ans.append(int("".join(list(j))))

ans.sort()
m=len(ans)
l,r=0,m-1
while l+1<r:
    k=(l+r)//2
    if ans[k]<n:
        l=k
    elif ans[k]>n:
        r=k
    else:
        l,r=k,k
        break

if ans[l]==n:
    print(l+1)
elif ans[r]==n:
    print(r+1)
elif ans[l]>n:
    print(l)
elif ans[r]<n:
    print(r+1)
elif ans[l]<n:
    print(l+1)
'''
if ans[l]>n:
    print(l)
elif ans[r]<=n:
    print(r+1)
else:
    print(l+1)
'''

answerC_better


from itertools import product
n=int(input())
ans=0
for i in range(3,10):
    l=list(product(["3","5","7"],repeat=i))
    for j in l:
        if len(set(j))==3:
            if int("".join(list(j)))<=n:
                ans+=1
print(ans)

D problem

Since there are several prime number related libraries prepared in C ++ and it often takes time to handle prime numbers in Python, I implemented it in C ++ (I realized later that it is not so difficult to do it in Python after all). It was.). Also, since I started implementing it before thinking about it, there was a lot of waste such as trying to make a table of prime numbers.

Below, we will consider the correct answer. First, we noticed that, as a famous fact, ** integers of 1 or more that have an odd number of divisors are in the form of a square **. Also, in the sample case, 32400 was written as 75, so if you take the route of 32400, you can see that it is $ 180 $, which is $ 32400 = 2 ^ 4 \ times 3 ^ 4 \ times 5 ^ 2 $. I also found that there was. Here I recall a famous fact that is very important in this matter. ** When a number is factored as $ \ prod_ {i = 1} ^ {n} p_i ^ {q_i} $ ($ p_i $ is a different prime number, $ q_i $ is an integer greater than or equal to 1), that number The total number of divisors of is $ \ prod_ {i = 1} ^ {n} (q_i + 1) $ **. Therefore, since the total number of divisors is 75, consider $ p_i $ (i = 1 ~ n) such that ** $ \ prod_ {i = 1} ^ {n} (q_i + 1) = 75 $. It's good **. If you look for $ q_i $ before looking for such $ p_i $, there may be four sets of (4,4,2), (14,4), (24,2), (74) ( At first, I was only thinking about (4,4,2) and was impatient.)

↓ The following seems complicated, but if you can consider it so far, it is not so difficult. Therefore, when N is given, 1 to N are factored into prime numbers and the number of each prime number contained in N! Is counted [1], the prime number contained in 2 or more, the prime number contained in 4 or more, 14 By counting and recording the prime numbers that include more than 24, the prime numbers that contain 24 or more, and the prime numbers that contain 74 or more, [2], (4,4,2), (14,4), (24) It can be obtained as an answer by calculating how many cases there are in each case of, 2) and (74) [3] and outputting the total.

✳︎ Prime_factorize is a function that factorizes into prime factors and puts it in a vector, and the amount of calculation is $ O (\ sqrt {n}) $ (I'm sorry if I make a mistake. I think I will publish an article in Qiita as a library later.)

answerD.cc


//Include
#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
#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 MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second

void Prime_factorize(vector<ll>& v,ll n){
    if(n<=1) return;
    ll l=ll(sqrt(n));
    FOR(i,2,l){
        if(n%i==0){
        Prime_factorize(v,i);Prime_factorize(v,ll(n/i));return;
        }
    }
    v.PB(n);return;
}

signed main(){
    ll n;cin >> n;
    map<ll,ll> m;
    //[1]
    FOR(i,1,n){
        vector<ll> v;Prime_factorize(v,i);
        REP(j,v.size()){
            if(m.find(v[j])==m.end()){
                m.insert(MP(v[j],1));
            }else{
                m[v[j]]++;
            }
        }
    }
    //[2]
    vector<ll> ans(5,0);
    for(auto i=m.begin();i!=m.end();++i){
        if(i->S>=74)ans[0]++;
        if(i->S>=24)ans[1]++;
        if(i->S>=14)ans[2]++;
        if(i->S>=4)ans[3]++;
        if(i->S>=2)ans[4]++;
    }
    //[3]
    ll rans=0;
    rans+=ll((ans[4]-2)*ans[3]*(ans[3]-1)/2);
    rans+=ans[0];
    rans+=(ans[1]*(ans[4]-1));
    rans+=(ans[2]*(ans[3]-1));
    cout << rans << endl;
}

Recommended Posts

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 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 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
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions
AtCoder Beginner Contest 067 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 081 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 060 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 103 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 092 Review of past questions
AtCoder Beginner Contest 099 Review of past questions
AtCoder Beginner Contest 065 Review of past questions
AtCoder Beginner Contest 053 Review of past questions
AtCoder Beginner Contest 094 Review of past questions
AtCoder Beginner Contest 063 Review of past questions
AtCoder Beginner Contest 107 Review of past questions
AtCoder Beginner Contest 071 Review of past questions
AtCoder Beginner Contest 064 Review of past questions
AtCoder Beginner Contest 082 Review of past questions
AtCoder Beginner Contest 068 Review of past questions
AtCoder Beginner Contest 058 Review of past questions
AtCoder Beginner Contest 043 Review of past questions
AtCoder Beginner Contest 098 Review of past questions
AtCoder Beginner Contest 114 Review of past questions
AtCoder Beginner Contest 045 Review of past questions
AtCoder Beginner Contest 120 Review of past questions
AtCoder Beginner Contest 108 Review of past questions
AtCoder Beginner Contest 106 Review of past questions