ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC044 D - 桁和 / Digit Sum

問題
提出コード
これが500点?という感じの難易度でした。苦手意識があり、全く違うベクトルの考察を始めてしまうので解ける気がしません…

解法

n \lt bのとき、s=nになります。それ以外でs=nになるようなbは存在しません。ということで、s=nの場合は、b=n+1が答えになります。この場合のみ、先に処理をします。
O(\sqrt{n})が間に合うので、どうにかして\sqrt{n}lognぐらいに計算量を落としたいです。
b進数について考えるとき、\sqrt{n}まではb進数になおすと3桁以上ですが、それより大きい数字(ただしn以下です)をなおすと2桁になります。
ということで、b\sqrt{n}におさまるパターンと、そうでないパターンで場合分けをしていき考えます。

  • b\sqrt{n}におさまるパターン
    O(\sqrt{n})が間に合うため、全探索ができそうです。
    桁和の計算もそこまで時間がかかりません(logにおさまります)。ということで、2から順番に調べていき、条件を満たすbが見つかった時点でうちきります。

  • b\sqrt{n}におさまらないパターン
    先ほど、こちらのパターンはb進数に直すと2桁となる、と言いました。
    2桁の数字を、"pq"と表現することにすると、b進数の定義から、
    n = p×b + q
    という条件が成り立ちます。
    また、問題の条件から、
    s = p + q を満たすようにしなければなりません。ということで、p,qについての方程式が2つできたので、これを連立します。上の式から、下の式を引くことで、
    n-s = p(b-1)
    という条件式になります。"b = "の形に直すと、
    b = \frac{n-s}{p} + 1
    となります。
    あとは、細かい条件をすべて満たしつつ、この方程式も満たすようなbの中で、最も小さいものを求めれば完了です。
    pについて探索すればいいのですが、s通り試していたのでは間に合いませんので、\frac{n-s}{p}が割り切れたときに、 p = \frac{n-s}{p}とおきなおして同時に調べれば、O(\sqrt{n-s} )で事足ります。
    あとは、

  • b \geqq q、つまりb \geqq s-p

  • b^{2} > n (これは、b\sqrt{n}におさまらないということを表しています)

  • n-s\geqq 0
    等の条件を加えて、全て満たすような場合のbの最小値を求めれば、答えになります。