２.Atcoder Grand Contest21 Digit Sum 2
A - Digit Sum 2
問題文
N 以下の正の整数の 10 進法での各桁の和の最大値を求めてください。
制約
- 1≤N≤1016
- N は整数である
自力では分からなかったので、正解者のコードを見て考察。
Nの条件から、全探索は不可能。
ですが、そもそも探索する必要がありません。
何故かというとN以下の正の整数の各桁の和が最大になるときは必ず、
・6999
・9
・89
・2999
先頭、一番左の桁以外が９になるからです。
０～９の整数の中で一番大きいのは９ですから当然ですね。
つまり、この問題は
１.桁の数 - １ 回合計に９を足す
２.先頭の桁の数字を合計に足す
という操作だけで十分そうです。
ですが、例えばN = 7000 のとき。
7000以下で各桁の和が最大値を取るのは、6999のとき、33です。
しかし、上の1、2の操作を行うと 9 + 9 + 9 + 7 = 34 となってしまいます。
ではどうやって解決するか。例を出して見ていきます。
N = 6997の時、各桁の和が最大値を取るのは 5999の時 32。
N = 5879の時、各桁の和が最大値を取るのは 4999の時 31。
N = 3279の時、各桁の和が最大値を取るのは 2999の時 29。
N = 114514の時、各桁の和が最大値を取るのは 99999の時 45。
規則性が見えてきたと思います。どれも最大値を取るのは 下N -1桁 が 9 の時。
そして、先頭桁の数が、-1 されています。
ここから、
1.桁の数 - １ 回合計に９を足す
2.先頭の桁の数字 - 1 を合計に足す
この二つの操作で求められそうです。
ちょっとまって！
それじゃ6999とか4999とか最初から先頭以外9の数字だとおかしくなるじゃん！
と思う方はちゃんと解き方を理解できています。
そうです。先の二つの操作だと、6999のときに、5999の各桁を足してしまいます。
ならばどうすればよいかと言うと
6999などの最初から先頭以外9の数字を存在できなくすればいいだけです。
は？と思うかもしれませんが理屈は簡単です。
１を足して繰り上げてしまえばいいのです。
7688でも、7933でも最大値をを取るのは6999の時だけです。別に1を足したくらいじゃに何も変わりません。
対して、6999に1を足せば7000です。
そして、7000の桁は４桁なので9+9+9
７から1を引いて６。
合計で３３です。 少し戻って確認してみてください。6999の時は33です。
なにも変わらないですね。
最終的に、問題を解くために必要な工程は３つ。
1.N に 1を足す
2.Nの桁数 - 1回合計に9を足す。
3.合計に先頭の数 - 1を足す。
これで、この問題は解決です。
