ABC169に参加しました

AtCoderのコンテストに参加した際の結果と考え方、反省点などを書いていきます。
コンテストページはこちら

解いた/挑んだ問題

A問題

問題の概要

A × Bを求める

制約

• 
• 
• 入力はすべて整数

どのように考えたか

制約が小さいのでオーバーフローを考慮せず掛け算したものを出力する

結果

一発AC
・提出したコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;


int main() {
    int a , b;
    cin >> a >> b;
    cout << a * b << endl;

    return 0;
}

最も早く解けた問題だったと思う

ACまでの時間

ACしたのはコンテスト開始から51秒です。

ABC169_A

B問題

問題の概要

N個の整数が与えられる。
N個の整数の積を出力せよ　ただし、積がを超える場合は代わりに'-1'を出力せよ

制約

• 
• 
• 入力はすべて整数

どのように考えたか

愚直に掛け算していくと、オーバーフローしてしまうので、
の定数(INF_)を用意し、これまでの整数の積(cnt)とINF_/入力された整数(a)を比較する
(cnt <= INF_/a)が偽の場合、cntに-1をいれる
その後、0が出てきたらcntに0を代入する

結果

提出したコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;
const ll INF_ = 1000000000000000000;


int main() {
    ll n, a,cnt=1;
    bool zero = false;
    cin >> n;
    cin >> cnt;
    rep(i, n-1) {
        cin >> a;
        if (zero && a != 0)continue;
        if (zero && a == 0) { cnt = 0; break; }
        if(cnt <= (INF_/a))
            cnt *= a;
        else {
            cnt = -1;
            zero = true;
        }
    }
    cout << cnt << endl;
    return 0;
}

<解いてみての感想を書く>

ACまでの時間

ACしたのはコンテスト開始から16分後です。

ABC169_B

C問題

問題の概要

A ×Bの小数点以下を切り捨て結果を整数として出力せよ

制約

• 
• 
• Aは整数
• Bは少数第2位まで与えられる

どのように考えたか

doubleにA,Bを入れ、floor関数で結果をlong longの変数に入れ出力

結果

コンテスト中に解けなかった
・提出したコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;
const ll INF_ = 1000000000000000000;


int main() {
    double a, b;
    cin >> a >> b;
    ll ans = floor(a * b);
    cout << ans << endl;
    return 0;
}

何がおかしいのか分からない(執筆時点)

ABC169_C

D問題

問題の概要

正の整数Nが与えられる
次の操作を最大何回行えるか求めよ<操作>

• ある素数のべき乗をzとする。
• Nがzで割り切れる
• 今回のzが以前の操作で選んだどのzとも異なる
• NをN/zで置き換える

制約

• 入力はすべて整数
• 

どのように考えたか

Nが割り切れる数は約数なので、約数を求めて約数が素数の場合、Nと割っていき、割れた数カウントする

結果

8回WAの末にAC
・提出したコード

#include"bits/stdc++.h"

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;
const ll INF_ = 1000000000000000000;

map< int64_t, int > prime_factor(int64_t n) {
    map< int64_t, int > ret;
    for (int64_t i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1) ret[n] = 1;
    return ret;
}

int main() {
    map<int64_t, int> m;
    auto aa = prime_factor(1000000007);
    ll n;
    int cnt = 0;
    cin >> n;
    set<ll>s;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            s.insert(i);
            if (i * i != n)s.insert(n / i);
        }
    }
    s.erase(1);
    for (auto itr : s) {
        if (n == 1)break;
        if (itr < 0)continue;
        m.clear();
        m = prime_factor(itr);
        if (m.size() != 1)continue;
        if (n % itr == 0) {
            n /= itr;
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

解き方に気づけはしたが実装が難しかった

ACまでの時間

コンテスト開始から97分後。

ABC169_D

結果

コンテスト結果

ABDの3完でした。
Cは取れなかったがDはとれてよかったです。

コンテスト成績表

順位、パフォーマンス変動

順位は前回より2500近く下がり4486位、レーティングは527となりました。

ABC169を終えた時点でのレーティング

反省点

今回はCが無理と悟り、すぐにD問題に移行できたのはよかったと思う
しかし、あてずっぽうに投げては意味がないので、次回からもう少し慎重に提出していきたい。