Mister雑記

競プロやります。

ARC099-D 「Snuke Numbers」 (500)

一番のトラウマ問題(2018/09/17時点)。

問題リンク

概要

正整数 nに対して、 nを10進法表記したときの各桁の和を S(n)とし、関数 g g(n) = \dfrac{n}{S(n)}と定義する。

そして任意の正整数 m \gt nに対して g(n) \leq g(m)が成立するような nを「すぬけ数」と呼ぶことにする。

このとき、すぬけ数を小さい方から順に K個出力せよ。

制約

  •  K \geq 1
  •  K番目のすぬけ数は 10^{15}以下である。

解説

ちょっと制約が変わっているが、これはすぬけ数が具体的にどれくらいの分布になっているかを悟られないようにするためのものだろう。

この問題の方針だが、大きく分けて2つある。1つはちゃんと計算してすぬけ数を順番に求める、言わば「正統派」。もう1つはある程度すぬけ数を求めるプログラムを作ってそこから法則を強引に見出す、言わば「エスパー派」である。

ここでは前者の方針をEditorialにしたがって解説するが、すぬけ数は列挙してみると結構面白い規則性があるらしいので調べてみるのもいいだろう。

方針

この問題で最も難しいのが、最初にどう一歩を踏み出すかというところである。

結論を言ってしまうと、今回の場合は以下のように漸化的にすぬけ数を求めることにする。

  •  snuke(n) = n以上で最小のすぬけ数」という関数 snukeを作る、
  • 1はすぬけ数なのでまず n = 1とする。
  •  n \leftarrow snuke(n + 1)として、 nを更新する。

自分一人でこの方針に向かえる気がしない。こういった方針立ても経験からくるものなのだろう。

というわけで次の課題は、関数 snuke(n)を作るということになる。

問題の有限化

すぬけ数の定義には「任意の正整数」が使われているが、これをプログラミングで扱うことはもちろんできない。

そこで、 snuke(n)上限というのを考えてみる。

 mがある程度大きいとき、 100m付近における gの最小値は m付近に比べて十分大きいことはなんとなく分かるだろうか。 mの桁数を dとすると、 100倍したところで桁和は高々 20程度しか増えないので、分母のように 100倍になるということはまずない1

というわけで、具体的に m \in (n, 100n]の範囲で g(m)が最小となる mを求めれば snuke(n)が求まることになる。

この「問題の有限化」がこの問題を解く上での1つの鍵である。これによって、「任意の m' \gt m \geq nに対して g(m) \leq g(m')」というプログラムでは到底扱えない性質が、まだ範囲こそ大きいが「 m \in (n, 100n]で g(m)が最小」というプログラムでも力技で扱える性質に帰着されたことになる。

ふるいにかける

上の議論によって「時間を気にしなければ一応は解ける」という状態にはなったが、まだ g(m)を求める対象が多すぎてとてもじゃないが現実的ではない。

そこで、すぬけ数となりうる値をある程度絞り込む必要がある。言うなれば調査対象を「ふるいにかける」というわけだ。

例えば、 n = 1000のとき snuke(1000) = 1234となりうるだろうか?答えはNOである。これはなぜかというと、例えば 1199という値は 1199 \lt 1234かつ S(1199) \gt S(1234)を満たすため明らかに g(1199) \lt g(1234)を満たすからだ。

このように、大半の値は「小さい方の桁は全部 9」という値が言わば上位互換として存在する。逆に、この性質を満たす値には自明な上位互換というのは存在しないため調べる必要がある。

具体例として、 n = 1234のときの調査対象を列挙すると以下のようになる。

4桁 3桁 2桁 1桁  0桁
1234 1235 1249 1399 2999
- 1236 1259 1499 3999
- ... ... ... ...
- 1239 1299 1999 9999
- - - - 10999
- - - - 11999
- - - - ...
- - - - 122999

1行目は nとの一致桁数である。一致する桁以降は全部 9というのが一番重要である。

そして上のリストに入る値は n \leq 10^{15} 300個にも満たないため、十分 g(m)を調べることが可能である。以上でようやく準備が整った。

実装例

#include <iostream>
#include <queue>

using namespace std;

using ll = long long;
template <typename T>
using GPQ = priority_queue<T, vector<T>, greater<T>>;

ll mypow(ll b, ll n) {
    return n == 0 ? 1 : b * mypow(b, n - 1);
}

// 桁和を求める
ll dsum(ll n) {
    ll ret = 0;
    while (n > 0) {
        ret += n % 10;
        n /= 10;
    }
    return ret;
}

// n以上で最小のすぬけ数を求める
ll snuke(ll n) {
    GPQ<pair<double, ll>> val;
    // (g(m), m)

    ll dig = 0;
    // 9が連続する桁数

    while (mypow(10, dig) <= n) {
        for (ll i = 1; i <= 9; ++i) {
            ll v = n - n % mypow(10, dig + 1) + i * mypow(10, dig) - 1;
            // 下dig桁が9
            // 1つ上は1~9
            // それより上はnと一致

            if (v >= n) {
                val.push(make_pair(v * 1.0 / dsum(v), v));
            }
        }
        ++dig;
    }
    --dig;

    // 1桁もnと一致しないものを列挙
    for (ll i = 1; i <= 100; ++i) {
        ll v = i * mypow(10, dig) - 1;
        if (v >= n) {
            val.push(make_pair(v * 1.0 / dsum(v), v));
        }
    }

    auto ret = val.top();
    // g(m)とmが最小となる(g(m), m)の組

    return ret.second;
}


int main() {
    ll K;
    cin >> K;
    ll pre = 1;

    for (ll i = 0; i < K; ++i) {
        cout << pre << endl;
        pre = snuke(pre + 1);
    }

    return 0;
}

 snuke関数で調査対象を列挙するときの以下のコード

ll v = n - n % mypow(10, dig + 1) + i * mypow(10, dig) - 1;

は前半のn - n % mypow(10, dig + 1) nの上位桁だけを取り出して、後半のi * mypow(10, dig) - 1で9が連なる値を加えている。

正直とても綺麗と言える実装ではないので、解き直す機会があれば差し替えたい。

感想

  • コンテストから3ヶ月経ったけど、やっぱこれムズいって。
    • 700点と言われても余裕で頷く。
  • こういう問題も圧倒的アルゴリズム力でねじ伏せられるようになりたい。

  1. 実のところ 100倍でも大きく取り過ぎで、 10倍くらいで十分である。ただ個人的に 10倍では不安があったので、ここでは以降も 100倍の範囲を取り続けることにする。