ARC034 B問題を解説する。 (PythonのACコードあり)

ARC034 B問題 方程式

問題

たとえば、$f(5391)=5+3+9+1=18$ のように、各桁の和を関数$f(x)$で定義する。
$1\leq N\leq 10^{18}$を満たす$N$が与えられるので、$x+f(x)=N$となる$x$を求めてください、という問題。

考察その1　xの上限は？

たとえば、$N=100$のとき、$x$は$100$以上の値をとりません。$100+f(100)>100$だからです。
どのような$N$が与えられても、$x<N$であることは間違いなさそうです。
これで$x$の上界が分かりました。

考察その2-1　xの下限は？

次に$x$の下限を考えてみます。
$N$の最大値は$10^{18}$なので、$x$を$1$から順番に全探索するとTLEになってしまいます。
もし実際に手計算で解くとなったときに、問題から$N=10^{18}$を与えられたら、だれも$x=1$から順番には計算していかないはずです。$10^{18}$よりも少し小さいところをくまなく探してみるんじゃないでしょうか。
この「少し小さい」がどの程度の数なのかを考えます。

考察その2-2　xの下限を求めていく

$x+f(x)=N$より、$x=N-f(x)$です。
たとえば、$f(x)$が$100$以下の値しかとらないことが分かっていれば、「$x=N-101$かなー？」と計算する必要がなくなります。
つまり、どれくらい下まで探索すればいいのかは、$f(x)$の最大値を求めるのと同じことになります。
$1\leq{N}\leq10^{18}$の範囲で、各桁の和が最大の数を考えると、9が18個だけ続いた数$99999999999999999$が最も大きくなりそうです。
実際には、$99999999999999999+f(99999999999999999)>10^{18}$となり、この数が答えになることはないですが、$f(99999999999999999)=9×18=162$で、$x=N-162$よりも下に答えがないことが分かりました。

考察その3　まとめ

正整数$N$が与えられたとき、
考察その1より、$x<N$、すなわち、$x\leq{N-1}$
考察その2より、$N-162\leq{x}$
２つを合わせて、$N-162\leq{x}\leq{N-1}$
この範囲で計162回の探索をすれば答えが出ます。

おまけ(ACコード)

def main():
    N=int(input())
    anslist=[]
    for i in range(1,163):
        x=N-i
        if x<0:
            break
        pl=0 #f(x)=pl
        sx=str(x)
        for k in sx:
            pl+=int(k)
        if pl+x==N:
            anslist.append(x)
    anslist.sort()
    print(len(anslist))
    for a in anslist:
        print(a)

if __name__ == '__main__':
    main()