I participated in AtCoder (ABC169 edition)

Hello! This is the roadrice field of a master's student in bioinformatics! It's been a while since I died from the last time, but since I participated in ABC169, please write down the entry.

Problem A

Multiplication up to 3 digits is learned by the third grade of elementary school in the current course of study.

My answer

A.py


A,B = map(int, input().split())
print(A*B)

B problem

I implemented it exactly as it was written once.

B.py



N = int(input())
A = list(map(int, input().split()))

ans = 1
for i in range(N):
    ans *= A[i]

if ans <= 1e18: print(ans)
else: print(-1)

The result is TLE. The numbers are big, right?

If there is 0 in the input, the answer is 0 at that moment, so if it is judged whether there is 0 in the input first, 0 is output without multiplication and the process ends, 10 18 during the calculation. If it exceeds </ sup>, I thought that it would be faster if I break there and output -1, so I wrote as follows.

B.py



N = int(input())
A = list(map(int, input().split()))

ans = 1
flg = True

if 0 in A: print(0)
else:
    for i in range(N):
        ans *= A[i]
        if ans > 1e18:
            flg = False
            break

    if flg: print(ans)
    else: print(-1)

By the way, this reduced the calculation time from the maximum 2206 ms to 56 ms. It will be considerably faster with a little ingenuity.

C problem

I knew it was about floating point, but it didn't work out ... I didn't study enough information technology ...

D problem

I used C ++ for this problem. You can maximize the number of operations by doing the following:

First, factor the given * N * into prime factors.


N = a^{6} \times b^{4} \times c^{3}  

Let z = a 1 </ sup>. Replace N with N / z. You can't choose the same z, so next is a 1 </ sup>, which is the next smallest a 2 < Select / sup> for z. Replace N with N / z.


N = a^{3} \times b^{4} \times c^{3}  

It still splits at z = a 3 </ sup>. Replace N with N / z.


N = b^{4} \times c^{3}  

Next, divide by z = b 1 </ sup> ...

Repeatedly dividing the prime factors by the 1st, 2nd, and 3rd powers, and if the prime factors are exhausted in * N *, divide by the 1st, 2nd, and 3rd powers of the next prime factors. You just have to repeat the process.

My answer

D.cpp



#include<bits/stdc++.h>
using namespace std;

vector<long long> pri_fac(long long N){
    vector<long long> yakusu;
    long long now = 0; 
    long long a = 2;
        while(N >= a*a){
            if(N%a == 0){
                yakusu.push_back(a);
                 N /= a;
            }else{
                a++;
            }
        } 
    if(N != 1) yakusu.push_back(N);
    return yakusu;
}

int main(){
    long long N;
    cin >> N;

    vector<long long> vec_all;
    vec_all = pri_fac(N);

    if(N == 1) cout << 0 << endl;
    else if(vec_all.size() == 1) cout << 1 << endl;
    else{
        long long now;
        now = vec_all[0];
        vector<long long> unique_count;
        unique_count.push_back(1);
        for(long long i=1;i<vec_all.size();i++){
            if(vec_all[i] != now) unique_count.push_back(1);
            else unique_count[unique_count.size()-1]++;
            now = vec_all[i];
        }

        long long ans = 0;

        for(long long i=0;i<unique_count.size();i++){
            long long j = 1;
            while(j <= unique_count[i]){
                ans++;
                unique_count[i] -= j;
                j++;
            } 
        }

        cout << ans << endl;
    }
    return 0;
}

When * N * is 1 or a prime number, I didn't want a bug, so I'm doing exception handling first. Pri_fac is a function that performs prime factorization and pushes the prime factors to vector.

Recommended Posts

I participated in AtCoder (ABC169 edition)
I participated in AtCoder (ABC158)
Atcoder ABC164 A-C in Python
Atcoder ABC167 A-D in Python
Atcoder ABC165 A-D in Python
Atcoder ABC166 A-E in Python
Atcoder ABC169 A-E in Python
AtCoder ABC177 A-D in python
I participated in the ISUCON10 qualifying!
Solve Atcoder ABC169 A-D in Python
I participated in PyData Tokyo Meetup # 2
AtCoder ABC176
I participated in Kaggle's NFL competition
AtCoder ABC177
I wanted to solve ABC159 in Python
AtCoder ABC 174 Python
AtCoder ABC187 Python
AtCoder ABC188 Python
AtCoder ABC 175 Python
Daily AtCoder # 2 in Python
Daily AtCoder # 6 in Python
Daily AtCoder # 18 in Python
Daily AtCoder # 53 in Python
Daily AtCoder # 33 in Python
Daily AtCoder # 24 in Python
Daily AtCoder # 37 in Python
Daily AtCoder # 8 in Python
Daily AtCoder # 42 in Python
Daily AtCoder # 21 in Python
Daily AtCoder # 17 in Python
Daily AtCoder # 38 in Python
Daily AtCoder # 54 in Python
Daily AtCoder # 11 in Python
Daily AtCoder # 15 in Python
Daily AtCoder # 47 in Python
Daily AtCoder # 13 in Python
Daily AtCoder # 45 in Python
I wrote a design pattern in kotlin Singleton edition
I wrote a design pattern in kotlin Adapter edition
Daily AtCoder # 30 in Python
Daily AtCoder # 40 in Python
Daily AtCoder # 10 in Python
Daily AtCoder # 5 in Python
Daily AtCoder # 28 in Python
Daily AtCoder # 39 in Python
Daily AtCoder # 20 in Python
Daily AtCoder # 19 in Python
Daily AtCoder # 52 in Python
Daily AtCoder # 3 in Python
Daily AtCoder # 14 in Python
Daily AtCoder # 50 in Python
Daily AtCoder # 26 in Python
Daily AtCoder # 4 in Python
Daily AtCoder # 29 in Python
Daily AtCoder # 22 in Python
Daily AtCoder # 49 in Python
Daily AtCoder # 27 in Python
Daily AtCoder # 1 in Python
I participated in competitive programming in a week after I started programming
Solve ABC169 in Python
Daily AtCoder # 25 in Python