#問題概要
問題のリンク
$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;
}
}