ABC044-D:桁和 / Digit Sum
問題
https://beta.atcoder.jp/contests/abc044/tasks/arc060_b
整数 に対して
進数の桁和
が与えられる。
を満たすような最小の
を求めよ。
制約
考え方
が大きいので単純に全探索はできない。そこで
で場合分けする。
(i) の場合
この場合は で全探索が可能である。
を
から順番に参照し、桁和を求める関数
の結果が
に等しい場合は、その
を出力すればいい。
(ii) の場合
この場合は を用いて
と
進数表示で表すことができる。また仮定より
である。
また より
となる。
より
を
の範囲で全探索して解を求めればよい。
Submission #2996291 - AtCoder Beginner Contest 044
どこに着目して考察するべきだったか
の制約から
は間に合わないが
は間に合う。また
では
と
進数で表すとシンプルな形になる。
は
と
に依存するので、
の範囲を定めるように式変形をすると全探索できる。
何がバグっていたか
得た知見
以上の
の
進数表示
- 変域を制限する式変形