3/22 AtCoder（ceilを使う時の注意、DP、N!を素因数分解）

ARC004C

二点間の距離がn個与えられて、点1と点nの距離の最小値はなんぼという問題

点が並んでる順番で距離が与えられているので、折り返すのは最長辺の両端でないといけない（逆にそこじゃないところで折ると長さが伸びてしまう）
求める値は、辺の長さの総和をS、最長辺の長さをmとして、max(0,2*m-S)になる

ARC062C

k = max(-(-A//L[i][0]),-(-B//L[i][1]))

と

k = max(math.ceil(A/L[i][0]),math.ceil(B/L[i][1]))

は同一のモノではないらしい（上の方が合ってる）
切り上げの時に安易にceil使うと間違えるかもしれない　原因不明　なにこれ

EDPC E　

価値iを達成するのに必要な最小の重量をdp[i]とするタイプのDP
こういうのは、まず全部float('inf')で埋めてから、dp[0]を0に更新して、リストのケツの方（つまりdp[10**5]）から値を更新していく　
dp[0]の方から更新していくと、例えば

weight value
3 30
4 50
5 60

という入力を受け取ったときに、dp[50]=4で更新→dp[100]を8で更新（重量4の品物を2回使っていることになるのでこの時点ですでにあり得ない）→......と無限に続いていってしまうので注意

ABC114D

約数を75個持つ数として、例えばp**4とq**14の積を考えたとき、このようにp,qを選んでくるときは
①pには、指数が4以上14未満の数を選び、qには指数が14以上のモノを選ぶ
②p,qいずれも指数が14以上のモノを選ぶ
の二パターンがあり、後者はnC2ではなくnP2（順番も考慮すれば、どちらを4つ、どちらを14つ使うかも考えたことになる）であることに注意して数え上げる

あと、階乗の素因数の個数を求めるコード

N = int(input())
def primes(n):
  ass = []
  is_prime = [True] * (n + 1)
  is_prime[0] = False
  is_prime[1] = False
  for i in range(2, int(n**0.5) + 1):
    if not is_prime[i]:
      continue
    for j in range(i * 2, n + 1, i):
       is_prime[j] = False
  for i in range(len(is_prime)):
    if is_prime[i]:
      ass.append(i)
  return ass
L = primes(N)
factorial_factor = []
for i in range(len(L)):
  k = L[i]
  cnt = 0
  cur = 1
  while N//k > 0:
    cnt += N//k
    cur += 1
    k = L[i]**(cur)
  factorial_factor.append([L[i],cnt])