AtCoder Regular Contest 067 参加記
はい。 oo-- 1315(+9)
http://arc067.contest.atcoder.jp
D問題のがチョロそうだったので先に取って、C問題はちょっと色々試してから解にたどり着いた後に2回コピペミスでペナ10分。。。
C - Factors of Factorial
Python3
def prime_t(t): i=2 while i**2<=t: if t%i==0: return 0 i+=1 return 1 p=[] for i in range(2,1008): if prime_t(i): p.append(i) d={i:0 for i in p} mod=10**9+7 n=int(input()) tmp=1 ans=1 R=[i for i in range(168)] for i in range(1,n+1): tmp*=i for j in R: while tmp%p[j]==0: d[p[j]]+=1 tmp//=p[j] if tmp<p[j]: break for i in d: ans*=(d[i]+1) ans%=mod print(ans)
素数を先に用意して素数で何回割り切れるか、素因数分解?のような何かをした。割り切れた回数+1(x0の場合があるため)の積が約数の個数になる。中間でかなり大きい数になるのでコマメに割っておくのが大事だと思う。
D - Walk and Teleport
Python3
n,a,b=[int(i) for i in input().split()] x=[int(i) for i in input().split()] ans=chk=0 for i in range(1,n): ans+=min(b,(x[i]-x[i-1])*a) print(ans)
双方向でコストが同じなので好きな場所に、町を飛ばしてコストBでテレポートしたほうが安くなることはなさそうな気がした(飛ばしてテレポートでも順々に移動の最小と同じコストになるまではありうるかな)。 なので順に隣に移動するコストA,Bの小さい方を選んだ場合の総和を解にした。
E,F問題は未着手で終わった。