Atcoder Regular Contest 034 A:主席、 B:方程式、 C:約数かつ倍数
ABCDの4問セット。CまではいつものARCよりも簡単。問題はこちら。
A: 主席
学生N人の5つの科目のテストの得点をそれぞれ与えられる。5つめのテストの点数だけ110/900倍するとして、もっとも得点の多い学生の得点を答える。
解法
問題文通りにやるだけ。
N = int(raw_input()) ans = 0 for loop in xrange(N): a,b,c,d,e = map(int,raw_input().split()) ans = max(ans, a+b+c+d+e*110./900.) print "%.6f"%ans
B: 方程式
f(123) = 1+2+3 のようにある数字の各桁を足し合わせた値を返す関数がある。正の整数N (≦ 1018)が与えられるので、正の整数xのうち x+f(x) = N となるようなxの個数とその値を答える。
解法
Nが大きいのですべての数について試すことはできない。しかし、Nは最大18桁で f(N) ≦ 9*18 = 162 であるので、N-200からNまでのxについて x+f(x) に代入してNになるかどうか確かめればいい。
def f(n): return sum(int(s) for s in str(n)) N = int(raw_input()) ans = [] for n in xrange(max(0,N-200),N+1): if n+f(n) == N: ans.append(n) print len(ans) for a in ans: print a
C: 約数と倍数
AとBが与えられる (1 ≦ B ≦ A ≦ 109, A-B ≦ 100)。A!の約数かつB!の倍数となる正の整数はいくつかあるかを100,000,007で割った余りで答える。
解法
A!の約数かつB!の倍数となれるのは、B!にA(A-1)...(B+1)が有している素因数を、(有している個数を超えない数で)任意の個数かけたものである。A!はB!にA(A-1)...(B+1)をかけたものであるので、上記の素因数の積によってできる数はA(A-1)...(B+1)の約数である。したがって、この素因数の積によってできた数にB!をかけると、問題文の条件を満たす数となる。つまり、やるべきはB+1からAまでの素因数の数をカウントすることである。
高校数学でも出てきたが、素因数p1,p2,p3...がそれぞれa1,a2,a3...個あったときに、これらの素因数の積から作ることのできる数は合計で、(1+a1)(1+a2)...個である。
from collections import defaultdict mod = 10**9+7 def calc(n): res = 0 i = 2 while i*i <= n: while n%i == 0: n /= i count[i] += 1 i += 1 if n > 1: count[n] += 1 A,B = map(int,raw_input().split()) count = defaultdict(int) for i in xrange(B+1,A+1): calc(i) ans = 1 for i in count.values(): ans = (ans*(i+1))%mod print ans