Mister雑記

競プロやります。

ARC090-F 「Number of Digits」 (900)

死ぬほどバグらせた。

atcoder.jp

概要

正整数 xに対し、 f(x) = xを10進数表記したときの桁数」と定義する。

整数 Sが与えられる。正整数の組 (l, r)で、 f(l) + f(l + 1) + \cdots + f(r) = Sを満たすものの数を 10^9 + 7で割った値を求めよ。

制約

  •  1 \leq S \leq 10^8

考察

※今回は考察が随分と遠回りだったので、解法だけ読みたい方は飛ばしてください。


最初に述べておくが、 10^n n + 1である。これを念頭に以下を読んでいただきたい。

以降、 d桁の数の個数を num(d)とする。これは num(d) = 9 \times 10^{d - 1}で求まる。

まず f(l) f(r)の桁数の差で場合分けすることにする。

 f(r) - f(l) = 0の場合

 f(l) = f(r) = dとする。このとき、 d桁の数は S / d個必要となる(ここから、 d Sの約数でなくてはならない)。この (l, r)の取り方は num(d) - d + 1個となる。

 f(r) - f(l) = 1の場合

 f(l) = dとすると、 d桁、 d + 1桁の数はそれぞれ dx + (d + 1)y = Sを満たす x, y個必要になる。よって拡張ユークリッドの互除法を使って気合で (x, y)の個数を求めればいける(いける)。

 f(r) - f(l) \geq 2の場合

そもそもこれを満たすのは l \lt 10^7のケースのみである。というのも num(8) \times 8 = 7.2 \times 10^8 Sの制約を上回るからだ。 よって f(r) \leq 9にて桁数のパターンを全部試し、上と同じように拡張ユークリッドの互除法で解の個数を...。

というところで力尽きた。理論上は可能なのだろうが、AtCoderはこういう重実装を出さない(と信じたい)。


ここで諦めてEditorialを見たが、それも f(r) - f(l) = 1のケースがよく分からなかった。そこでkmjpさんの記事を見つけた。こちらは「区間で全探索する」という方針で f(r) - f(l) \leq 1を統一的に扱っていて、とても分かりやすかった。

kmjp.hatenablog.jp

解法

上と同様に d桁の数の個数を num(d)とする( num(d) = 9 \times 10^{d - 1})。

 l \lt 10^8の場合

 (l, r)を全探索する。 (l, r)はともに単調増加なので、尺取り法の要領で十分高速にシミュレートできる。

 l \lt 10^7でも f(r) - f(l) \geq 2のケースは網羅できるのだが、そうしない理由は後で分かる。

 l \geq 10^8の場合

以降 f(r) - f(l) \leq 1となる。

 t = r - l + 1として、 tを全探索することにする。このとき f(l) = \lfloor S / t \rfloorとなる1が、 l \geq 10^8 \Rightarrow f(l) \geq 9 (ここ注意) より f(l) \lt 9になったら終了する。

ここで以下の2つのケースに分けられる。

 S \bmod t = 0のとき

このとき \lfloor S / t \rfloor桁の数が t個必要となる。これは上で述べた f(r) - f(l) = 0のケースなので、上の式を適用すればいい。

 S \bmod t \gt 0のとき

このとき \lfloor S / t \rfloor \lfloor S / t \rfloor + 1の間に区間が跨るようになるので、高々1通りになる。

問題は「 \lfloor S / t \rfloor桁の数と \lfloor S / t \rfloor + 1桁の数は十分あるのか?」だが、 l \geq 10^8 num(9) = 8.1 \times 10^8 \gt Sから常に足りることが分かる。これが先程 l \lt 10^7にしなかった理由である。

実装例

前半の全探索部分はいくらC++といえども結構ギリギリなので、無駄を極力削る必要がある。

以下のコードは214msで通る。

#include <iostream>

using namespace std;
using ll = long long;

const ll MOD = 1000000007;

template <typename T, typename U>
T mypow(T b, U n) {
    if (n == 0) return 1;
    if (n == 1) return b % MOD;
    if (n % 2 == 0) {
        return mypow(b * b % MOD, n / 2);
    } else {
        return mypow(b, n - 1) * b % MOD;
    }
}

int main() {
    int S;
    cin >> S;

    ll ans = 0;
    int r = 0, sum = 0;
    int ldig = 0, rdig = 0, lten = 1, rten = 1;

    // l<10^8 尺取り法で全探索
    for (int l = 1; l < 100000000; ++l) {
        if (l == lten) ++ldig, lten *= 10;

        while (sum < S) {
            ++r;
            if (r == rten) ++rdig, rten *= 10;
            sum += rdig;
        }

        if (sum == S) ++ans;
        sum -= ldig;
    }

    // l>=10^8 区間長で総当たり
    for (int t = 1; t * 9 <= S; ++t) {
        int d = S / t;
        if (S % t == 0) {  // f(l)=f(r)=dの場合
            ans += mypow(10LL, d - 1) * 9 - t + 1 + MOD;
        } else {  // f(l)=f(r)-1=dの場合
            ++ans;
        }
    }

    cout << ans % MOD << endl;
    return 0;
}

ちなみにFastest Code辺りは考察で述べた拡張ユークリッド互除法の解法を実装しているらしい。正気か?

反省

  • 脳を使うことはC++に任せよう。
  • 区間長で全探索するのは中々出ない。
    •  f(l)の桁数に囚われすぎてしまった。
  • 学びが大きい問題ではあった。

  1.  \lfloor S / t \rfloor \times t \leq S \lt ( \lfloor S / t \rfloor + 1) \times tより従う。