ABC340をpythonで解く

　ABC340の問題文は問題 - 鹿島建設プログラミングコンテスト2024（AtCoder Beginner Contest 340）へ。

A

　for文で簡単に実装できます。

A,B,D=map(int,input().split())
for i in range (A,B+1,D):
    print(i,end=" ")
print()

B

　普通に指示通りにappendするのと後ろからk番目の値を出力するのをやるだけ。後ろからk番目はA[-k]で出すのが簡単。

Q=int(input())
query=[list(map(int,input().split())) for _ in range (Q)]
A=[]
for i,j in query:
    if i==1:
        A.append(j)
    else:
        print(A[-j])

C

　黒板に出てくる数字の種類はそこまで多くはならないので、(出てくる数字,個数)を管理して操作をやっていけば普通にシミュレーションできます。

N=int(input())
now=[(N,1)]
next={1:1}
ans=0
while next:
    next=dict()
    while now:
        x,kosuu=now.pop()
        if x<=1:
            continue
        ans+=x*kosuu
        if x%2==0:
            if x//2 not in next.keys():
                next[x//2]=kosuu*2
            else:
                next[x//2]+=kosuu*2
        else:
            if x//2 not in next.keys():
                next[x//2]=kosuu
            else:
                next[x//2]+=kosuu
            if x//2+1 not in next.keys():
                next[x//2+1]=kosuu
            else:
                next[x//2+1]+=kosuu
    for x,kosuu in next.items():
        now.append((x,kosuu))
print(ans)

D

　与えられた情報からedgeを作ってダイクストラで解きます。最近のDの中では素直で優しい問題な感じがします。

from heapq import *
N=int(input())
ABX=[list(map(int,input().split())) for _ in range (N-1)]
edge=[[] for _ in range (N)]
for i in range (N-1):
    A,B,X=ABX[i]
    edge[i].append((i+1,A))
    edge[i].append((X-1,B))
jikann=[-1]*N
q=[(0,0)]
heapify(q)
while q:
    now,at=heappop(q)
    if jikann[at]!=-1:
        continue
    jikann[at]=now
    for next,tuika in edge[at]:
        if jikann[next]==-1:
            heappush(q,(now+tuika,next))
print(jikann[-1])

E

　区間可算遅延セグ木使えば解ける気がするけどEで遅延セグ木出すか？それ以外の解き方は思いつかん。

以下リンク
ABC339/ホーム/ABC341