AtCoder AGC 021 A - Digit Sum 2 (灰色, 300 点)

少し慎重に

• 問題へのリンク

問題概要

以下の正の整数の 10 進法での各桁の和の最大値を求めよ。

制約

• 

考えたこと

とかだったら答えは になりそうだ。一般に、

の形をしたものだけ考えれば良さそう。仮に とかが最適解だったとしても、その場合は として、 も最適解になるのだ。このような議論を深めれば、"" の形のみ考えれば良いことがわかる。

具体的には、 の桁数を 、最上位の桁の値を としたとき、 として次のようになる。

• ( が 個) ならば、これが答え
• ( が 個) ならば、 が答え
  • であっても、問題ない

計算量は 。

コード

実装上は、あらかじめ に 1 を足しておくといい感じ。そうすると統一的に

• の最上位の桁の値を 1 減らす (0 になってもよい)
• それ以外の桁の値を 9 にする

としたものが答えとなる。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long N;
    cin >> N;
    ++N;
    long long res = 0;
    while (N) {
        if (N < 10) res += N-1;
        else res += 9;
        N /= 10;
    }
    cout << res << endl;
}