【AtCoder】ABC 406 B - Product Calculator | 緑コーダーが解くAtCoder

atcoder.jp

配点: 200 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: ??? / NoviSteps: 5Q

問題概要

高橋君は電卓を持っており、電卓には最初 が表示されている。

これから、電卓に対して 回の操作を行い、 [tex i] 回目の操作では、その時点で画面に表示されている数に正の整数 を掛ける。しかし、電卓には 桁までしか表示できないため、計算結果が 桁以上になる場合、代わりに が画面に表示される。そうでない場合は正しく計算結果が表示される。

回の操作の後に電卓に表示されている数を求めよ。

制約

• 
• 
• 
• 入力は全て整数

考察

基本的には操作を行うごとに電卓の表示をシミュレーションしていけばよいのだが、 の制約がネックとなる。

の制約から、 は最大で オーダーであり、電卓の表示桁数によってはlong long型をもってしてもオーバーフローしてしまう。

このオーバーフローを回避する方法として、ここでは2つのやり方を挙げる。

__int128_tでゴリ押す

gcc コンパイラの拡張として、__int128_tという整数型が存在する。これは 128 bit の範囲まで扱うことができる変数型で、intやlong longと同じように四則演算できるものの、標準ではcinやcout、型変換などが用意されていないことに注意したい。

したがって、実装例では一度stringに直してから答えを出力している。

自前で実装したい場合は以下を参照。

kenkoooo.hatenablog.com

式変形で割り算の形にする

回目の操作前に電卓に が表示されていたとする。このとき、操作後の計算結果が 桁以上になるという条件は、以下のように書き換えられる。

※ 実装時に整数除算を用いる都合上、閾値を とはしていない。

ここで、 と はどちらも 以下であるから、long long型を用いればオーバーフローを起こさずに計算できる。

実装例

考察1

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

using ll = long long;

// ======================================== //

int main()
{
    int N, K;
    cin >> N >> K;

    ll limit = 1;
    rep(i, 0, K)
    {
        limit *= 10;
    }

    __int128_t now = 1;
    rep(i, 0, N)
    {
        ll A;
        cin >> A;

        now *= A;

        if (now >= limit)
        {
            now = 1;
        }
    }

    string ans;
    while (now > 0)
    {
        int d = (int)(now % 10);
        ans = char('0' + d) + ans;
        now /= 10;
    }

    cout << ans << endl;

    return 0;
}

atcoder.jp

考察2

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

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

using ll = long long;

// ======================================== //

int main()
{
    int N, K;
    cin >> N >> K;

    ll limit = 1;
    rep(i, 0, K)
    {
        limit *= 10;
    }
    limit--;

    ll now = 1;
    rep(i, 0, N)
    {
        ll A;
        cin >> A;

        if (now > limit / A)
            now = 1;
        else
            now *= A;
    }

    cout << now << endl;

    return 0;
}

atcoder.jp

実装時間: 10分

コメント

オーバーフローでひっかけてくる系の問題は、言語仕様で有利不利変わってくるのであまり好きではない。

一応、C++でも boost ライブラリを用いれば多倍長整数を扱えるので紹介しておく。

boostjp.github.io