tooh’s diary

半角全角、常体敬体が入り乱れるカオス

3/19 AtCoder(PyPy3)

こんにちは。気分が悪くて半日お布団の中にいたとーです。

AtCoder

ARC013A

以前解けなかったきりしばらく放置していた問題

荷物の長さの順列を持ってきて、与えられた容器の辺をその順列の第一、二、三要素で割り切って、掛け合わせたものが容器に入る荷物の数なので、それの最大値を求めるだけ


ABC110D

これも以前解けなかった問題

素因数分解して、指数の部分を分割すればよいっていう賢いやり方が書いてあった すごい

さて実装の段で、nCkをかけていって、最後に10**9+7で割る操作が入ったのだが、

import math
n = int(input())
k = int(input())
a = (math.factorial(n))%(10**9+7)
b = (math.factorial(k)%(10**9+7))
c = (math.factorial(n-k)%(10**9+7))
print((a*pow(b*c,10**9+5,10**9+7))%(10**9+7))

この逆元を使うやり方だとTLEし、

n,k = map(int,input().split())
cur = 1
for i in range(k+1,n+1):
  cur *= i
for j in range(1,n-k+1):
  cur = cur//j
print(cur%(10**9+7))

こっちの普通に掛け算をする方では通った なんで

多分n,kがそんなに大きくないときは、後者の計算量もそれほどではないのでこっちの方が速い(nCk自体の計算はkに依存するので)のではないかとか思ったけど、n=10**5,k = 100とかでも前者の方が速かった(し、後者に至っては間に合わない)ので何とも言えない

まあこういうケースもあるということを覚えておく



EDPC D,I

どっちもTLEだったけどPyPyにしたら通った  マジ?

PyPyを使うデメリットは分かってないけど、速いんだったらこっちの方がよくないですか