AtCoder参加したったー（ABC169編）

こんにちは！バイオインフォマティクス系オタク修士学生のroadricefieldです！前回から死ぬほど間が空いていますがABC169に参加したのでその参戦記をば.

A問題

3桁までの掛け算は現行の教育指導要領では小学3年生までに習います.

私の解答

A.py

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

B問題

一回書いてあるとおりに実装してみました.

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)

結果はTLE. 数字も大きいですし, ですよねといった感じです.

入力に0があればその瞬間答えは0なので最初に入力に0がないかを判定してあれば掛け算を行わずに0を出力して終了, 計算中も途中で10¹⁸を超えればそこでbreakして-1を出力するようにすれば速くなるだろうと考え以下のように書きました.

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)

ちなみにこれで計算時間が最大2206 msから56 msまで落ちました. ちょっとの工夫でかなり速くなるものですね.

C問題

浮動小数点の話なのは分かっていたのですが色々やってもうまく行きませんでした...情報技術の勉強が足りなさすぎる...

D問題

この問題ではC++を使用しました. 以下のように操作することで操作数を最大にできます.

まず, 与えられたNを素因数分解します.

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

z = a¹とします. NをN/zに置き換えます. 同じzは選べないので次はa¹の次に小さいa²をzに選びます. NをN/zに置き換えます. ここまでで

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

となりました. まだz=a³で割れます. NをN/zに置き換えます. これで

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

となりました. 次はz=b¹で割ります...

というように素因数の1乗, 2乗, 3乗で割っていくことを繰り返していき, 途中でその素因数がNの中で尽きたら次の素因数の1乗, 2乗, 3乗で割っていくことを繰り返せばいいわけです.

私の解答

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

Nが1だったときや素数だったときはバグって欲しくなかったので最初に例外処理をしています. pri_facは素因数分解を行なってひたすら素因数をvectorにpush_backする関数です.