読者です 読者をやめる 読者になる 読者になる

AtCoder Regular Contest 034 参加記

atcoder

はい。 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 です。