【世界一わかりやすい】Atcoder ABC247 C・D問題 Python3解説

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$ を求め、値を保存しておこう(｀・ω・´)

コード

C.py

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/

コード

D.py

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問題とか、過去問の解説上げてくかも。
来週も頑張ろうね(｀・ω・´)ｷﾘｯ