👋

ABC 238 C - digitnumのメモ

2022/10/19に公開

AtCoder

競プロ

tech

目についたC問題を解いてみるの回です。

考察

Nの成約が非常に大きいので、 $O(N)$ でも間に合いません。となるとある程度まとまった単位で計算する必要があります。桁単位で考えるのがよさそうです。

桁の最小値（ $N$ が1桁の場合は1、それ以外なら10の倍数）の場合の合計値は必ず1ですね。桁数が同じでないといけないので、どんなに大きい数でも桁内での最小値なら1です。
では桁の最大値だとどうなるか。桁の最大値は9だけで構成される数ですね。これはたとえば99なら90、999なら900、9999なら9000となります。これはちょっと計算が面倒そうだったので愚直実装で求めました。
法則を見出すならこれで十分です。つまりこれは桁の最大値から桁の最小値-1を引いた数です。考えてみれば、そりゃそうですね。
それで、この90とか900はあくまでも桁の最大値単体での合計値です。桁全体での合計値は、最小値から最大値までのそれぞれの合計値を全て足す必要があります。
それぞれの合計値ですが、単体で見ると1ずつ増えるはずです。10なら1（10だけ）、11なら2（10、11）、12なら3（10、11、12）というように。なので、桁全体の合計値を求めるには、1から桁の最大値の場合の合計値までの数字を全て足せばいいことになります。
1ずつ増える数列の合計値を求めるのは、最小値を $a$ 、最大値を $b$ とすると一般的に $(a + b) * (b / 2)$ で求められますね。これなら $O(1)$ で求められます。
桁ごとの計算量が $O(1)$ で、桁数は最大でも19桁なのでこれで計算量としては全く問題なさそうです。

これを全ての桁で計算してその合計値を求めればいいですが、 $N$ が属する桁については、 $N$ 自体が桁の最大値となります。検証してみましたが、その場合でも全く同じ計算が適用できるようでした。

ただ注意が必要なのは、 $N$ の場合の合計値が奇数だった場合は上記の計算式では結果が狂います。その場合は $N-1$ までの合計値を求めた後にNを足せばいいですね。
また、 $N$ が桁の最小値だった場合は、Nが属する桁の合計値は必ず1なので計算しなくていいです。

$N$ が1桁の場合なども考えてみましたが、特に考慮は必要なく同じように計算できそうでした。

あとは随時modをとれば解けそうですね。

提出コード

コンテスト中じゃないのでゆっくりコメントを書きながら実装しました。

import java.math.BigInteger

fun main() {
    val n = readLine()!!.toBigInteger()

    val mod = BigInteger("998244353")

    // Nが属する桁と、それより桁が少ない数を別々に考える
    val length = n.toString().length - 1
    var ans = BigInteger.ZERO

    // Nが属する桁より1少ない桁までの合計値を求める
    for(i in 1..length) {
        // 桁の最大値
        val max = "9".repeat(i).toBigInteger()
        // その桁の答え
        val sum = calcSum(max)
        ans = (ans + sum) % mod
    }
    // Nが属する桁の合計値を求めて足す
    val sum = calcSum(n)
    ans = (ans + sum) % mod

    println(ans % mod)
}

fun calcSum(max: BigInteger): BigInteger {
    // 桁の最小値
    val min = "1".plus("0".repeat(max.toString().length - 1)).toBigInteger()
    if(max == min) {
        return BigInteger.ONE
    }

    // 桁の最小値の答え（常に1）
    val minSum = BigInteger.ONE
    // 桁の最大値の答え
    val maxSum = max - min + BigInteger.ONE

    // 全体の答え
    return if(maxSum % BigInteger.TWO == BigInteger.ZERO) {
        (maxSum + minSum) * (maxSum / BigInteger.TWO)
    } else {
        val tmp = maxSum - BigInteger.ONE
        (tmp + minSum) * (tmp / BigInteger.TWO) + maxSum
    }
}

$N$ が属する桁と、それより小さい桁を分けて計算しています。 $N$ はどのような数かわからないので。 $N$ が1桁の場合はループに入らず、 $N$ が属する桁を求めるほうの計算だけが実行されて結果的に合います。

実装中に気づいたのですが、このアルゴリズムだと瞬間的にLongを超える数値になりそうでした。なので結局BigIntegerを使っています…
そういう型を使わなくてもオーバーフローしないためのmodなのでなんかおかしいですね。また、桁の最小値や最大値を求めるのにStringを経由しているのも想定解ではなさそうです。まあでも解けたのでいいやと思いましたｗ

考察

提出コード

Discussion