[PYTHON] AtCoder Beginner Contest 114 Review of past questions

Time required

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;
}