はじめに
先週出られなかったので2週間ぶりの参加です。
成績：ABC3完（600）
A
AをBになるまでDずつ増やしていくとしか言いようがない。
while文で書いたが、range関数を出力すればそれでよかった。
A
a, b, d = map(int, input().split())
ls = [a]
num = a
while num < b:
num += d
ls.append(num)
print(*ls)
B
pythonのappendの仕様そのままなので、言われた通り実行していく。リストを後ろから見るときは-1番目からスタートなので考えやすい。
B
q = int(input())
A = []
for i in range(q):
n, k = map(int,input().split())
if n == 1:
A.append(k)
if n == 2:
print(A[-k])
C
制約が$2\le n \le10^{17}$なので、愚直にやると全然間に合わない。
そこで、nを$\lfloor n/2 \rfloor$と$\lceil n/2 \rceil$に分割していく作業を考えると、$\lfloor log_2(n) \rfloor$回まではこの作業によって払う金額はn円で、最後の1回で払う金額は$2・(n-2^{\lfloor log_2(n) \rfloor})$となることに気づく。（証明はできていないが…）
という訳でこれを実装するのだが、桁数が大きくなるとlogが正しく機能せず1WAを喰らったので$\lfloor log_2(n) \rfloor$については数え上げで対応した。
C
import math
n = int(input())
x = 2
cnt = 0
while x <= n:
x = x*2
cnt += 1
price = n * cnt
price += 2 * (n - 2**cnt)
print(price)
なお想定解はメモ化再帰であったらしい。nをすべて1にするまでに支払う金額をf(n)と定義すれば再帰的に解けるとのこと。
再帰関数の類はまだ馴染みがないのでグラフと合わせて勉強していく必要があるだろうな～。
C-official
from functools import cache
@cache
def f(N):
if N == 1:
return 0
else:
return f(N//2) + f((N+1)//2) + N
n = int(input())
print(f(n))