問題：AtCoder Beginner Contest 233: E - Σ[k=0..10¹⁰⁰]floor(X／10^k)

解説

$\sum_{k=0}^{10^{100}} \lfloor \frac{X}{10^k} \rfloor$

を計算せよという問題。

Xの制約が

$1 <= X < 10^{500000}$

と大きいし、k=0から10¹⁰⁰まで計算は普通にしていたら制限時間に間に合わない。

Xの桁数が最大500000なので、問題をエスパーすれば計算量O(桁数)で解くのかなぁと当たりはつくが、まだどうすればいいのかわからない。

とりあえず紙に書いてみる。

するとなんか法則性が見えてくる。

特にX=98764のとき、98764 + 9876 + 987 + 98 + 9 + 0 + ... と一桁ずつ減っていくのを足し算する形になっていることに気づけば、他のパターンも同様になっていることに気づく。

他に思いつかないし、じゃあこれを愚直にプログラムに落とし込んで書いたコードが以下の形。（TLEする）

配列ansは、答えの各桁の数字を格納する。

void __solve() {
    // TLE lol
    string X; cin >> X;
    const ll MAX_ANS = 500010;
    vector<ll> ans(MAX_ANS);

    while(X.size()!=0) {  // 最大 (桁数) 回
        string tmpX = X;
        ll i = 0;
        while(tmpX.size()!=0) {  // 平均 (桁数+1)/2 回
            ans[i] += tmpX[tmpX.size()-1] - '0';
            if (ans[i] >= 10) {
                ans[i+1] += ans[i]/10;
                ans[i] = ans[i] % 10;
            }
            tmpX = tmpX.substr(0, tmpX.size()-1);
            i++;
        }
        X = X.substr(0, X.size()-1);
    }
    for(ll i=0; i<MAX_ANS; i++) {
        if (ans[i] >= 10) {
            ans[i+1] += ans[i]/10;
            ans[i] = ans[i] % 10;
        }
    }


    // 出力
    bool is_still_zero = true;
    for(ll i=MAX_ANS-1; i>=0; i--) {
        if (is_still_zero && ans[i]==0) continue;
        if (ans[i] != 0) is_still_zero = false;
        printf("%lld", ans[i]);
    }
    printf("\n");
}

書いたあとから気づくのだが、最初のwhileループが最大 桁数 回、二個目のwhileループが平均 (桁数+1)/2 回実行されるので、だいたい計算量O((桁数)²)程度となり、これはTLEする。

コンテスト中はTLEして終了。

寝て起きたら解法が思いつく。こんなことってあるんですね。

X=987654のときのものを、筆算の形で書いてみたのが以下の形。

各桁が累積和になっていることに気づく。

累積和はO(桁数)で計算できる。

各桁の数字の計算も、累積和を使えばO(桁数)で計算できる。

よって線形時間で解けた。

この「筆算の形で考えると解法が見えてくる」というのは、ABC231: E - Minimal paymentsでも見たので、結構よくあるテクニックかもしれない。

コーナーケース

特になし

実装

C++で実装した。

#define _USE_MATH_DEFINES  // M_PI等のフラグ
#include <bits/stdc++.h>
#define MOD 1000000007
#define COUNTOF(array) (sizeof(array)/sizeof(array[0]))
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define intceil(a,b) ((a+(b-1))/b)
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<long,long>;
const long long INF = LONG_LONG_MAX - 1001001001001001;
void chmax(int& x, int y) { x = max(x,y); }
void chmin(int& x, int y) { x = min(x,y); }


void solve() {
    string X; cin >> X;
    const ll MAX_ANS = 500010;
    vector<ll> ans(MAX_ANS);

    // 累積和作成
    vector<ll> r(X.size()+1, 0);
    for(ll i=X.size()-1; i>=0; i--) {
        r[i] = r[i+1] + (X[X.size()-1-i]-'0');
    }

    // ans作成
    for(ll i=0; i<X.size(); i++) {
        ans[i] += r[i];

        ans[i+1] += ans[i]/10;
        ans[i] = ans[i]%10;
    }

    // 出力
    bool is_first_zero = true;
    for(ll i=MAX_ANS; i>=0; i--) {
        if (ans[i]==0 && is_first_zero) continue;
        if (ans[i]!=0) is_first_zero = false;
        if (!is_first_zero) {
            printf("%lld", ans[i]);
        }
    }
    printf("\n");
}

int main() {
    solve();
    return 0;
}

ベスパリブ

プログラミングを主とした日記・備忘録です。ベスパ持ってないです。

ABC233: E - Σ[k=0..10^100]floor(X／10^k) を解いた

解説

コーナーケース

実装