今回はPythonでABC413をABDを解くことができたので、備忘録を纏めました。
コンテスト概要
デンソークリエイトプログラミングコンテスト2025（AtCoder Beginner Contest 413）
開催日:2025年6月28日 21:00-22:40
方針
各品物の大きさAの合計が、カバンの大きさMより小さいならYes、大きいならNoを返す。
N, M = map(int,input().split())
A = list(map(int,input().split()))
if sum(A) M:
print("Yes")
else:
print("No")
方針
$N$種類の文字列$S$に対して、相違なる整数$i,j$を選び$S_{i}$と$S_{j}$をこの順で連結した際に文字列としてあり得るものは何通りあるかを求める問題。$N$の制約が小さいため、二重ループにしてもTLEにならない。
N = int(input())
S = [input().strip() for _ in range(N)]
res = set()
for i in range(N):
for j in range(N):
if i != j:
c = S[i] + S[j]
res.add(c)
print(len(res))
方針
この問題は、リスト操作ではTLEになるため、dequeを使用して効率的に、2種類のクエリを処理する必要がある。
- 追加クエリ（形式:
1 c x）: 値xをc個、末尾に追加 - 削除 & 合計クエリ（形式:
2 k）: 先頭からk個削除し、その合計値を出力
追加処理
Aに(x, c)の形式で追加することで、重複データを圧縮して保存可能。
if query[0] == '1':
c = int(query[1])
x = int(query[2])
A.append((x, c)) # 値xをc個追加（まとめて）
削除 & 合計クエリ
常に先頭から順に必要な数だけ取り出して、合計を計算。
必要な分だけ取り出した後は、deque を更新。
else:
k = int(query[1])
total = 0
while k > 0:
x, c = A[0] # 先頭の（値, 個数）を確認
if c k:
total += x * c
k -= c
A.popleft() # 全部使い切ったので削除
else:
total += x * k
A[0] = (x, c - k) # 一部だけ使う → 個数を減らす
k = 0
ans.append(str(total))
全体
from collections import deque
import sys
input = sys.stdin.readline
Q = int(input())
A = deque()
ans = []
for _ in range(Q):
query = input().split()
if query[0] == '1':
c = int(query[1])
x = int(query[2])
A.append((x, c))
else:
k = int(query[1])
total = 0
while k > 0:
x, c = A[0]
if c k:
total += x * c
k -= c
A.popleft()
else:
total += x * k
A[0] = (x, c - k)
k = 0
ans.append(str(total))
print('\n'.join(ans))
結果
ABC 3完
順位 4028th / 11733
パフォーマンス 807
レーティング 475 → 535 (+60)
感想
前回と比べてパフォーマンスがだいぶ下がってしまいました。
引き続き次回レートを伸ばせるように精進しようと思います。
Views: 1
