agc 044 a (python) - aacord’s memo

0完。カス。これが最後のレートつくAGCだったと思うとまあ残り５分で迷いながらもBを提出したのは良かったかも知れない。レート変動ないものを頑張る意味はないのでAGCは今後出ないでしょう。
今日学んだこと。
math.ceil は 15 桁以上の数字は勝手に丸めるので

from math import ceil as C
print((99999999324399925+1)//2)
print(C(99999999324399925/2))
print((99999999324399925)/2)

とやると

49999999662199963
49999999662199960
4.999999966219996e+16

となるため１番目と２番目が一致しなくなって A で永久に１WAを吐いていた。
コンテスト中はそもそもそこまで到達してないけど。AもBも誤読して終わった。まだ寝てた方が有意義だったかも。
メモ化再帰は from functools import lru_cache とかいうのが便利らしい。
お守りみたいにいつもの dfs の上に貼っただけなので仕組みは知らない。
Nから k にするコストを一回求めてあったらその計算をもう一度繰り返すのを回避する仕組みがあるらしい。

A の解法については、N を何回で１にするかで考えると、最小でNを小さくしていく動作の候補は、全部１ずつ引くのを別にすると、
途中で 2, 3, 5 で割ることになる。
ただし N が割り切れる数になるまでは１で引いたり、足したり！する必要がある。
例えば N = 77 とすると
77 → -1 → 76 →/2→ 38,... と減らしていくことも最小の手順の候補になりえるし、
77 → +1 → 78 →/2→ 39,... と減らしていくことも最小の手順の候補になりえる。一旦+1にして結果39 にした方が３でそのまま割れたりするので -1 より得な場合もある。
しかし、２で割る場合はそのまま割る, +1, -1 以外の動作は遠回りとなる。
例えば、5 →-3→ 2 →/2→ 1 と遷移する方が 5 →-1→ 4 →/2→ 2 →/2→ 1 よりもコストが小さくなるなら、そもそも最初から全部１ずつ引いた方がコストが小さくなる。
Nが奇数の時は(N-3)//2 ＝(N-1)//2-1 になるので、回数が余分に増えているので無駄。

2とか＋3とかする場合も同じようにして無駄だと分かる。

よって dfs(N) から dfs(N//2)+a+(N%2)*d, dfs((N+1)//2)+a+(-N%2)*d とループをつくればよい。
３や５の場合も同じ。

import sys
sys.setrecursionlimit(10**9)
from functools import lru_cache

t = int(input())
  
for _ in range(t):
    n,a,b,c,d = map(int,input().split())
    @lru_cache(None)
    def f(k):
      if k == 1:return d
      if k == 0:return 0
      return min(k*d, f(k//2)+a+k%2*d,f((k+1)//2)+a+-k%2*d, f(k//3)+b+k%3*d,f((k+2)//3)+b+-k%3*d, f(k//5)+c+k%5*d,f((k+4)//5)+c+-k%5*d)
    print(f(n))