水面下の夢

競プロやイラストに興味があります.メインブログがここ.同人サークル「かのらぶ」のページはこっち( https://yumechi0525.amebaownd.com ).ブログアイコンはYaQ(@8_9_00)さんから.

今日の競プロ(2015/05/29)

(これこそ昨日なのでは… 日時管理がガバガバ)

ARC 034 B

問題

B: 方程式 - AtCoder Regular Contest 034 | AtCoder

回答

Submission #417614 - AtCoder Regular Contest 034 | AtCoder

桁数が多いので,総当りは当然TLEする.
条件式から,fは最大の時でも,f(999999999999999999) = 162なので,せいぜいN - 200くらいを調べれば良いことに気がつく.N < 200の時は全範囲を検索.また,条件に上がっているfだが,pythonならばこれで値を得られる.

sum(list(map(int, str(i))))

よって,こんな感じになりました.

ran = 9 * 18
N = int(input())
low = (N - ran - 1) if N > (ran + 1) else 1
res = []
for i in range(low, N):
    if i + sum(list(map(int, str(i)))) == N:
    	res.append(i)
 
print(len(res))
for r in res:
    print(r)

該当するものの個数を表示してから,該当するものを表示という流れなので,一旦リストに置かざるを得ないと思います.

追記

部分点解放も載せておく.

Submission #417701 - AtCoder Regular Contest 034 | AtCoder

N = int(input())
res = []
for i in range(N):
    if i + sum(list(map(int, str(i)))) == N:
    	res.append(i)
 
print(len(res))
for r in res:
    print(r)


なんとなく数学的なセンスも少しついたなと思います.
ぱっとどこらへん辺りまで調べればいいのか,ということを思いつけるのは慣れが大きいのかも.
(最近は素数とか,組み合わせとかの存在を自然と考慮できるようになった)

改めて数学がやりたくなってきたのですが,時間がないですねw
競プロで問題を解きながら勉強していこう…