This page looks best with JavaScript enabled

ABC148E – Double Factorial

 ·   ·  ☕ 2 min read  ·  ✍️ reud · 👀... views

ここまでDiff低めなコンテスト中々無くない・・・?

珍しい下振れなコンテストでしたね!

12分でDまで解いてパフォ800の世界怖い・・・・

そしてE問題です。

E - Double Factorial

末尾に10がある⇨2*5の組み合わせがいくつあるかって言う話です。

こういった問題は、TLE解を実装してから解答を作ると、比較できて滅茶苦茶良いのですが、TLE解間違ってると終了します。

なんでこんなこと書いているかって言うと、私はこれで終了したからです。

例えばf(12)の際末尾に0が何個並ぶと思います?

12,10,8,6,4,2,1を掛けるので1になるのは和英とさくっとわかると思います?

では、100の場合は?

100,90,80,70,60,50,40,30,20,10ですよね

これ、11じゃないんです。

私、これに気づくのに1時間かかりました。

何をやらかしたかって、TLE解を間違えたのでそもそも間違っていることに気づかない地獄パターンへ・・・・

辛いね。

ちなみにこんな感じのコードでACできます。

#include <bits/stdc++.h>

#define INF 1e9
using namespace std;

#define REPR(i, n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()

template<class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

typedef long long ll;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

ll solve(ll N) {
    ll st5 = 10;
    ll ans = 0;
    while ((st5 / 2) <= N) {
        ans += N / st5;
        st5 *= 5;
    }

    return ans;
}

int main() {
    ll N;
    cin >> N;
    ll ans = ((N % 2) == 0) ? solve(N) : 0;
    cout << ans << endl;
    return 0;
}

提出 #9114526 - AtCoder Beginner Contest 148

Share on

reud
WRITTEN BY
reud
Stundent