ABC413の感想戦
デンソークリエイトプログラミングコンテスト2025（AtCoder Beginner Contest 413）に参加して、A, B, Cの３問のみ正解できました。
A - Content Too Large
カバンの大きさ\(M\)と品物の大きさ\(A_i\)が与えられるので、カバンに全ての品物を入れられるかを答える問題。
考え方
品物の大きさを合計して、カバンの大きさと比較する。
技術的工夫
Pythonでは、List型の合計をsum()で求めることができるので、これを使用すればループしながら加算する必要がない。
n, m = map(int, input().split())
a = list(map(int, input().split()))
if sum(a) <= m:
print("Yes")
else:
print("No")B - cat 2
問題： B - cat 2
\(N\)個の文字列\({S_1, S_2, \cdots S_N}\)が与えられるので、任意の\({i, j}\)の組み合わせで作成できる文字列の種類を答える問題。ただし\(i \ne j\)で、異なる組み合わせでも作成できた文字れるが同じならば１つと数える。
考え方
競技プログラミングの基本は二重ループをいかに無くすかがポイントです。そのため全ての組み合わせを作成するのは良い考えではないと思います。しかしB問題なので、難しく考えずに単純に全ての組み合わせを作成しても制限時間を超えないと予想して、そのとおりにしました。
技術的工夫
異なる組み合わせでも結果として作成された文字列が同じならば同一の文字とするので、作成された文字列をSet型に入れることで重複を排除する。
n = int(input())
s = []
for _ in range(n):
s.append(input())
concat = set()
for i in range(n):
for j in range(n):
if i != j:
concat.add(s[i] + s[j])
print(len(concat))C - Large Queue
問題： C - Large Queue
空の数列\(A\)がある。二種類のQueryが与えられるので、この\(A\)に各Queryを順番に処理した結果を表示する問題。
- タイプ1:
1 c xは、\(A\)の末尾にc個のxを追加する。 - タイプ2:
2 kは、\(A\)の先頭からk個の数字を削除して、その削除した部分の合計を出力する。
考え方
実際にList型を作成して各項にxを代入していくのは、制限に時間を超えてしまうことが予想できる。そこで、同じxが塊として\(A\)に追加されるので、xとcの組み合わせとして記録しておく。
タイプ2を処理して数字を削除するときも、実際に\(A\)を操作すると制限時間を超えてしまう。そこで、実際に\(A\)を操作して数字を削除するのではなく、どこまで削除したかをポインタを使って管理する。この時、最後の項は途中まで削除されいくつか残る場合が有る。この場合は、cの値を更新する。
Q = int(input())
que = []
index = 0
for _ in range(Q):
q = list(map(int, input().split()))
match q[0]:
case 1:
que.append({"num": q[1], "val": q[2]})
case 2:
size = q[1]
length = 0
sum = 0
for i in range(index, len(que)):
length += que[i]["num"]
sum += que[i]["val"] * que[i]["num"]
if length == size:
print(sum)
length = 0
sum = 0
index = i + 1
break
elif length > size:
over = length - size
sum -= que[i]["val"] * over
print(sum)
que[i]["num"] = over
index = i
break