【AtCoder】ABC 387 C - Snake Numbers | 緑コーダーが解くAtCoder

atcoder.jp

配点: 350 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1249

過去開催された ABC のC問題の中でトップレベルの Diff となった問題。ABC の admin である snuke さんもコンテスト終了後にこう発言するレベル。

すみません、ABC-C 難しすぎました・・・
— ꑄ꒖ꐇꌅꏂ🐾 (@snuke_) 2025年1月4日

問題概要
制約
考察
実装例
コメント

問題概要

$10$ 以上の正整数のうち、10進数表記したときに先頭の桁の数字がそれ以外のどの桁の数字よりも真に大きくなるようなものをヘビ数と呼ぶことにする。

$L$ 以上 $R$ 以下のヘビ数の個数を求めよ。

制約

$10\leq L \leq R \leq 10^{18}$
入力は全て整数。

考察

問題ではある範囲内のヘビ数の個数を問われているが、これを直接求めるのは難しい。したがって、以下のような関数 $f(x)$ を定義する。

$f(x) :=$ $1$ 以上 $X$ 以下のヘビ数の個数

なお、求める答えは $f(R) - f(L - 1)$ と書くことができる(「以上」なので $f(L)$ は含むことに注意)。

$L, R$ は最大で $10^{18}$ オーダーになるので、単純な数え上げでは TLE してしまう。

そこで、 $x$ の桁数を $n$ 、 $x$ の各桁を左から順に $x_1, x_2, \cdots, x_n$ として、 $n$ 個の枠に左から順に $0$ から $9$ の数字を当てはめていくことを考える( $i$ 桁目に当てはめられる数字の上限は $x_i - 1$ )。

先頭の枠を 0 としたとき

具体例で考えよう。 $x = 100$ とする。

このとき、左から $i$ 番目の枠を $d_i$ とすれば、 $0 d_2 d_3$ と表せる。この下で、(先頭の $0$ を無視した)全体がヘビ数となるように $d_2, d_3$ に適当な数字を当てはめていく。

$d_2 = 9 \Rightarrow d_3 = 8, 7, \cdots, 0$ : 計9個
$d_2 = 8 \Rightarrow d_3 = 7, 6, \cdots, 0$ : 計8個

$\cdots$

$d_2 = 2 \Rightarrow d_3 = 1, 0$ : 計2個
$d_2 = 1 \Rightarrow d_3 = 0$ : 計1個

先頭から2桁目を数字を決定したら、3桁目にはそれ未満の数字しか入れることができない。

$n$ 桁で考えると、2桁目の数字を $a \: (1 \leq a \leq 9)$ と決定したら、3 から $n$ 桁目には $0, 1, \cdots, a - 1$ の $a$ 個の数字しか入れることができない、ということだ。

では一般化してみよう。

(先頭の $0$ を無視した)全体が $k$ 桁の数 $00 \cdots 0 d_{n-k+1} d_{n-k} \cdots d_n$ に対して、 $d_{n-k+1} = a$ としたときのヘビ数の個数は、 $a^{k-1}$ 個である。

※ $d_{n-k} \cdots d_n$ の $k - 1$ 桁に入れられる数字には、 $0, 1, \cdots, a - 1$ の $a$ 個の候補がある。

1桁の数はヘビ数には当てはまらないことを踏まえると、 $k = 2, 3, \cdots, n - 1$ までの和を取ればよい。つまり、この場合のヘビ数は全部で $\displaystyle \sum_{k = 2}^{n - 1} \sum_{a = 1}^{9} a^{k-1}$ と計算することができる。

先頭の枠を x_1 未満の数字としたとき

$x = 472$ とすると、

$322, 321, 320, 312, 311, 310, 302, 301, 300$
$211, 210, 201, 200$
$100$

がこの場合のヘビ数として当てはまる。

一般化すると、 $a d_2 d_3 \cdots d_n \: (1 \leq a \lt x_1)$ という場合である。この場合、 $d_2 \cdots d_n$ の $n - 1$ 桁に入れられる数字には $0, 1, \cdots, a - 1$ の $a$ 個の候補があることになる。

...つまり、先ほどの「先頭の枠を $0$ としたとき」と同様の考え方である。したがって、この場合のヘビ数は全部で $\displaystyle \sum_{a = 1}^{x_1 - 1} a^{n-1}$ と計算することができる。

それ以外のとき

この問題の本質的な部分。ここでは、複数の例を挙げる。

例えば、 $x =47211$ であるとき。

$x_1 = 4$ であるので $d_1 = 4$ は確定し、 $4 d_2 d_3 d_4 d_5$ の状態となる。このとき、 $d_2$ から $d_5$ に入れられる数字の候補は $0, 1, 2, 3$ である。これは、今までのケースと変わらない。

では、 $x = 51243$ のときはどうだろうか。

$x_1 = 5$ であるので $d_1 = 5$ は確定し、 $5 d_2 d_3 d_4 d_5$ の状態。

ここで $d_2 = 0$ とすれば、以降の $d_3, d_4, d_5$ には $0, 1, 2, 3, 4$ のどれを入れても $x$ 以下のヘビ数になる。

しかし、 $d_2 = 1$ とすると、 $d_3$ では $0, 1, 2$ のいずれかしか選べない。もし $3, 4$ を入れると元の $x$ を超えてしまうからだ( $x = 51243 \lt 513 d_4 d_5$ )。

この制限は後ろの $d_4, d_5$ についても同様。 $d_4$ には $0, 1, 2, 3$ 、 $d_5$ には $0, 1, 2$ のみ入れることができる。

今度は $x = 51743$ を考えてみる。

直前と同じように $d_2 = 1$ を選んで $51 d_3 d_4 d_5$ の状態であるとする。

$d_3$ では $0, 1, 2$ しか選べない... と思いきや、この場合は $0$ から $4$ まで選ぶことができ、さらに $d_4, d_5$ も同様に $0$ から $4$ まで候補となる。

ここまでの例を見ていくと、 $d_i$ に入れられる数字の候補として、

$0, 1, \cdots, x_1 - 1$ の $x_1$ 個
$0, 1, \cdots, x_i$ の $x_i + 1$ 個

の2つの場合があることが分かった。これらの違いは何だろうか。

それは、 $x_1 \leq x_i$ となる $i \: (2 \leq i \leq n)$ が存在するかどうかである。

$d_2$ から $d_n$ に入れられる数字の最低条件は $0, 1, \cdots, x_1 - 1$ であるが、もしこのような $i$ が存在するのならば、これらの数字のどれを選んでも元の $x$ を超えることはない。したがって、この時点で先述の方法で計算できる。

逆に $x_i \lt x_1$ となる桁があった場合は、この条件がさらに厳しくなり $0, 1, \cdots, x_i$ となる。ただし、この制約は $d_i$ にのみ適用され、 $d_{i+1}$ 以降はまた $x_{i+1} \lt x_1$ かどうかを見る必要がある。

まとめると、 $i = 2, 3, \cdots, n$ と見ていって、

$x_1 \leq x_i$ ならば、 $d_i$ から $d_n$ までの $n - i + 1$ 桁それぞれに $0, 1, \cdots, x_1 - 1$ の $x_1$ 個の数字どれかを入れられることが確定するので、この場合のヘビ数は $x_1^{n - i + 1}$ と計算できる。
ならば、にはの数字どれかを入れられる。
- $0, 1, \cdots, x_i - 1$ の数字を入れた場合、以降の $d_{i+1}$ から $d_n$ までの $n - i$ 桁には $0, 1, \cdots, x_1 - 1$ のいずれかを入れても元の $x$ は超えないので、この場合のヘビ数は $\displaystyle \sum_{j = 0}^{x_i - 1} x_1^{n - i} = x_i x_1^{n - i}$ と計算できる。
- $x_i$ を入れた場合、 $d_{i+1}$ 以降の桁に入れる数字によっては元の $x$ を超える可能性があり、この時点では計算できないのでスキップ。

最後まで $i$ を見たとき、スキップしていたもの(すべての $i$ について $d_i = x_i$ であるもの)もヘビ数に該当するので、答えに加算する。

実装について

以上で、ヘビ数のすべてのケースについて場合分けすることができた。あとはこれを実装していく。

基本的には上述の計算をコードに落とし込むだけだが、累乗の処理は少し気を付けたい。今回は $10^{18}$ オーダーまで扱うので、 C++ 標準のpow関数を使うと浮動小数点の誤差が生じる可能性がある。

実装例では繰り返し二乗法による累乗の処理をしていうが、素直に

long long int_pow(long long x, long long a) {
    long long res = 1;
    for (int i = 0; i < a; i++) res *= x;
    return res;
}

のように書いてもよい。

なお、実装例では 0-indexed になっていることに注意。

実装例

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

constexpr int INF = 1e+9;

using ll = long long;

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

ll pow_int(ll x, ll n)
{
    ll res = 1;
    while (n > 0)
    {
        if (n & 1)
            res *= x;
        x *= x;
        n >>= 1;
    }
    return res;
}

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

ll f(ll x)
{
    string s = to_string(x);
    ll n = s.size();
    ll top = s[0] - '0';

    if (n == 1)
        return 0;

    ll res = 0;
    rep(k, 2, n) rep(a, 1, 10) res += pow_int(a, k - 1);

    rep(a, 1, top) res += pow_int(a, n - 1);

    rep(i, 1, n)
    {
        ll d = s[i] - '0';
        if (d >= top)
        {
            res += pow_int(top, n - i);
            return res;
        }
        else
        {
            res += d * pow_int(top, n - i - 1);
        }
    }

    res++;

    return res;
}

int main()
{
    ll L, R;
    cin >> L >> R;

    cout << f(R) - f(L - 1) << endl;

    return 0;
}