atcoder.jp
問題
- 整数Nが1つだけ黒板に書かれてるよ
- 2以上の整数が全てなくなるまで、以下の操作を繰り返すよ
- 2以上の整数を1つ選んで、$x$とする
- $x$を1つ消して、$\lfloor \frac{x}{2} \rfloor$と、$\lceil \frac{x}{2} \rceil$を
- この操作で、お金が$x$円かかるよ
- 最終的に操作が行えなくなるまでにかかる金額はいくら？
成約
- $1 \leq N \leq 2 \times 10^{17}$
思考
- もしNが0なら…0円。
- もしNが1なら…0円。
- もしNが2なら…2を選んで2円→1が2個できるので、2円+(0円+0円) = 2円
- もしNが3なら…3を選んで3円→1と2が1個ずつできるので、3円+(0円+2円) = 5円
- もしNが4なら…4を選んで4円→2が2個できるので、4円+(2円+2円) = 8円
- 何か、再帰関数っぽい、見た目をしている。
- 1が1つだけ書かれている時のコスト〜Xが1つだけ書かれている時のコストがわかっていたら、X+1が1つだけ書かれているときのコストはすぐ出てくる、けど…
- $10^{17}$は、なぁ…流石にdpテーブル作るのは、重たい…
- ので、頑張って、再帰関数を、書く
- メモ化しようね
- dict使っても良いけど、lru_cacheで一撃。便利。
コード
from functools import lru_cache
N = int(input())
@lru_cache(maxsize=None)
def f(x):
if x == 0 or x == 1:
return 0
return x + f(x//2) + f((x+1)//2)
print(f(N))
