ABC044 D - 桁和 / Digit Sum
問題
提出コード
これが500点?という感じの難易度でした。苦手意識があり、全く違うベクトルの考察を始めてしまうので解ける気がしません…
解法
のとき、になります。それ以外でになるようなは存在しません。ということで、の場合は、が答えになります。この場合のみ、先に処理をします。
が間に合うので、どうにかしてかぐらいに計算量を落としたいです。
進数について考えるとき、までは進数になおすと3桁以上ですが、それより大きい数字(ただし以下です)をなおすと2桁になります。
ということで、がにおさまるパターンと、そうでないパターンで場合分けをしていき考えます。
がにおさまるパターン
が間に合うため、全探索ができそうです。
桁和の計算もそこまで時間がかかりません(logにおさまります)。ということで、2から順番に調べていき、条件を満たすが見つかった時点でうちきります。がにおさまらないパターン
先ほど、こちらのパターンは進数に直すと2桁となる、と言いました。
2桁の数字を、"pq"と表現することにすると、進数の定義から、
という条件が成り立ちます。
また、問題の条件から、
を満たすようにしなければなりません。ということで、についての方程式が2つできたので、これを連立します。上の式から、下の式を引くことで、
という条件式になります。""の形に直すと、
となります。
あとは、細かい条件をすべて満たしつつ、この方程式も満たすようなの中で、最も小さいものを求めれば完了です。
について探索すればいいのですが、通り試していたのでは間に合いませんので、が割り切れたときに、とおきなおして同時に調べれば、で事足ります。
あとは、、つまり
(これは、がにおさまらないということを表しています)
等の条件を加えて、全て満たすような場合のの最小値を求めれば、答えになります。