AtCoder AGC021 A - Digit Sum 2(300点)

問題概要

問題のリンク

$N$ 以下の正の整数の $10$ 進法での各桁の和の最大値を求めてください。

制約条件

• $1≤N≤10^{16}$
• $N$ は整数である

考えたこと

やることは一見とてもシンプル！$1$から$N$までの整数を、それぞれ各桁の和をとっていき最大値を求めたい。
だが制約をみたらわかる通り、全探索はとても間に合わない。

求めたいのは最大値なのでできるだけ9が多いほうがいいのは自明である。よって$(N-1)*9+N桁目の値f$が答えとなる。この時、$N$の$1$から$N-1$桁目が全て9である場合、$f$は$N$桁目の値であるが、そうでない場合、$N$桁目の値 - $1$が$f$となる。(そうしないと$N$より大きい値の各桁の和をとることになるので。)

解答

a.cs

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args) {
        long n = long.Parse(Console.ReadLine());
        long l = digitLength(n);
        long f = digitFirst(n);
        Console.WriteLine((l-1)*9 + f);
    }
    static long digitLength(long x) {
        long length = 0;
        while(x>0) {
            length++;
            x /= 10;
        }
        return length;
    }
    static long digitFirst(long x) {
        long first = 0;
        List<long> digit = new List<long>();
        while(x>0) {
            first = x%10;
            digit.Add(x%10);
            x/=10;
        }
        for(int i = 0; i < digit.Count()-1; i ++) {
            if(digit[i] != 9) {
                first -= 1L;
                break;
            }
        }
        return first;
    }
}