問題：https://atcoder.jp/contests/agc021/tasks/agc021_a?lang=ja
任意の正の整数Nが与えられた際に、それ以下の数で各桁の数字を足し合わせた和が最も大きくなる数字を求めて、各桁の和を回答する問題。
整数の各桁をどのように取得するか、またN以下で各桁の和が最大になるのはどのような条件か、考察が必要となる。
たとえば、サンプルケースで言えば「100」が与えられた時、100以下で各桁の和が最大なのは99(和は18)。サンプルケース2では9995に対して、9989(和は35)が最大となる。
ここで行っているのは、「ある桁Mにおいて9でない数字が現れたときに、Mより一つ大きい桁の数を1減らして、M桁以降の数を全て9にすると言う操作」である。全部の桁が9ならば何もせずに桁を足し合わせれば最大となる。たとえばある桁の数字が「8」だった場合は、上の位の数字を1引いて、8を9に変えても差し引きゼロではあるが、処理を分けるのも大変なので9以外は全て同じ動作で処理して構わない。
コード例
N=input()
N=list(N)
for k in range(len(N)):
N[k]=int(N[k])
ans=0
pos=0
for i in range(1,len(N)):
if N[i]!=9:
N[i-1]=N[i-1]-1
pos=i
break
if pos==0:
print(sum(N))
else:
for j in range(pos):
ans+=N[j]
ans+=9*(len(N)-pos)
print(ans)10進数の各桁をどのように取得するかがまず問題だが、pythonの場合、標準入力で受け取る際にintで受け取らず、あえてstrで受け取ると言う方法が使える。strはリストのようにインデックスを指定して、一桁づつ要素にアクセスできるからだ。
上のコードでは一旦文字列で受け取ったあと、リストに変換している。ただリストに変換しただけだと、中身が文字列のままで処理しづらいので、for文で全ての要素をintに変換し直して四則演算ができるようにした。
あとは、一番上の桁をのぞいて9以外の数字の桁が出てくるかチェックし、9以外の数字が出てきたときには、その一つ前の桁を-1して、今見ている桁は9に置き換える。現在上から何番目の桁を見ていたかをposに記録しておく。
もし、posが初期値の0のままなら、そのまま桁を足し合わせるのが最大値となる。リストなのでsumでそのまま足せば答えになる。
posに0以外の数字が入っている場合、どこかで9でない桁があったと言うことになる。9以外の数字がでた桁までをfor文で足し合わせ、それ以下の桁を全て9として足し合わせたのが回答である。
10進数の各桁の取得方法
def digits_sum(N):
sum=0
while N/10!=0:
sum+=N%10
N//=10
return sum10進数の各桁を取得するために、文字列で取り込んでリスト化して対応したが、オーソドックスな方法としては、上であげたコードが存在する。上記のコードでは各桁の数値を順番に求めてその総和を返すようになっている。
アルゴリズムとしては、対象を10で割った商が0になるまで10で割り続け、得られる余りが各桁の数字になる、と言う仕組みだ。
たとえば198なら、
198を10で割って、商は19、余りは8。一桁目は8。
次に19を10で割って、商は1、余りは9。二桁目は9。
次に1を10で割って、商は0、余りは1。三桁目は1。
商が0になったので、計算終了。