Edited at

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;
}
}