名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

今日の競プロ(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
競プロで問題を解きながら勉強していこう…