ABC247のC,D問題を、Python3で解説します!
ょゎょゎな筆者でもわかる、読みやすさを重視した、初心者向け解説です(´・ω・`)
ゆっくり見ていってね(`・ω・´)キリッ
C問題 『1 2 1 3 1 2 1』
問題ページ:C問題 - 1 2 1 3 1 2 1
考え方
$S_n=S(n-1)+n+S(n-1)$ であることより、再帰的に解けば効率が良い(`・ω・´)
$i = 1$ から $n$ まで、順に $S_i$ を求め、値を保存しておこう(`・ω・´)
コード
n = int(input())
S = [[1]] #S_0は1で定義しておく
for i in range(1, n):
#i=1~nまで、順にS_iを求め、Sに保存していく
S.append(S[i-1] + [i+1] + S[i-1])
print(*S[n-1]) #「*リスト」でリストの要素をスペース区切りで出力できるよ
D問題 『Cylinder』
問題ページ:D問題 - Cylinder
考え方
$x=1$ の時、筒に入れたボールを、$(x, c)$ の形で、右に追加していく。
$x=2$ の時、筒のボールを左から順に取り出していく。
取り出しすぎたら、取り出しすぎたボールの個数を更新して、左から戻す。
筒の中身は、dequeを使えば、右からも左からも $O(1)$ で取り出すことができる(`・ω・´)
dequeについて(他サイトより引用させていただきました)
https://note.nkmk.me/python-collections-deque/
コード
q = int(input())
from collections import deque
balls = deque([]) #ここにx=1の時、筒に入れたボールを、(x, c)の形で、右に追加していく
for i in range(q):
query = list(map(int, input().split()))
if query[0]==1: #x=1の場合
x = query[1]
c = query[2]
balls.append([x, c]) #(x, c)の形で、右に追加
else: #x=2の場合
c = query[1]
s = 0 #取り出したボールの数を0で初期化
ans = 0 #答えを0で初期化
while c>s: #cを超えない限りボールを取り出す
b = balls.popleft() #左から取り出す
s += b[1] #取り出したボールを追加
ans += b[0]*b[1] #答えを追加
balls.appendleft([b[0], s-c]) #取り出しすぎた分を左から戻す
ans -= b[0]*(s-c) #取り出しすぎた分を答えから引く
print(ans)
まとめ
最後まで見てくれてありがとう(´・ω・`)
これからも自分の勉強がてらABCのC,D問題とか、過去問の解説上げてくかも。
来週も頑張ろうね(`・ω・´)キリッ