AtCoder Regular Contest 067 参加記

はい。 oo-- 1315(+9)
http://arc067.contest.atcoder.jp
D問題のがチョロそうだったので先に取って、C問題はちょっと色々試してから解にたどり着いた後に２回コピペミスでペナ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(x⁰の場合があるため)の積が約数の個数になる。中間でかなり大きい数になるのでコマメに割っておくのが大事だと思う。

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問題は未着手で終わった。