AtCoder Regular Contest 034 参加記
はい。 oxxx でした。一応はB問題は部分点20取ったんですが。。
Aは提出したものでBはちょっと悔しかったんでやり直したものを記載。
http://arc034.contest.atcoder.jp
A - 首席
N人のうちで最高得点のものを出力する。
n=int(raw_input()) ans=0 while n: n-=1 l=map(int,raw_input().split()) ans=max(ans,sum(l[:4])+(l[-1]*110.0/900)) print ans
塗り絵って多分マークシートのことかな。計算した点数を配列に保存しておいてソートするか、毎回比較して大きい方を保存しておくかだと思う。
B - 方程式
たとえばNが101の時に、x=91とf(x)=f(91)=10でNと等しい101になるようなxを探す。f(x)の計算方法は各桁の全ての和。
ans=[] n=int(raw_input()) for i in xrange(max(1,n-153),n): f=sum([int(x) for x in str(i)]) if i+f==n: ans.append(i) print len(ans) if len(ans): for i in ans: print i
f(x)として最大で使うかもしれないのは1018-1で9が17個あるときの総和の153です。これより大きいf(x)はxだけでNより大きくなってしまうのでx+f(x)=Nという等式を成立させることが出来なくなります。
またf(x)から153より大きい数を作ることが出来ないということはx+f(x)=Nのxの探索もNから153を引いたものか、1のどちらか大きい方からだけみれば大丈夫なはずです。それより離れた範囲からは等式が絶対に成立しないためです。
おそらく考え方というか10の何乗かとかで一見大きい数のようで実は9*制限桁数という問題はcodeforcesにも過去ありました。。その時も勿論気づけずで今回のatcoderでも引っかかりました。。。。
codeforcesの類似問題(だと思う)は http://codeforces.com/contest/460/problem/B です。