どうもこんにちは！
今週のコンテストはCまで完答。Dは途中でギブアップ。
C問題はABCを始めた頃は全く解けなかったんですが、そろそろD問題の勉強をはじめてもいい頃になったかもと思うこのごろです。
今回はCまでを振り返ります。
※ 2025/7/9 D問題を追加しました。
問題
問題は以下のリンクから。
A - Content Too Large -
数列とある値Mが与えられ、数列の各要素の合計値がM以下となるかそうでないかを判定する問題。
数列の合計はsumで計算して、if文で判定して回答を出力するとしました。
n,m = map(int,input().split())
s = [int(x) for x in input().split()]
print("Yes" if sum(s) <= m else "No")
B - cat 2 -
与えられたn個の文字列から異なる2つの文字列を連結して文字列を作るとして、文字列が何通りあるかを回答する問題。このとき同じ文字列が複数個できた場合でも1通りと数えます。例えばa, a, atcoderが与えられたとしたら、aa, aatcoder, atcoderaの3種類となります。
与えられる文字列は最大100個で、全部の組み合わせを見ても10000個ないぐらいです。全部の組み合わせの文字列を作ってリストに入れて、集合にして重複を削除した個数を出力するとしました。
n = int(input())
s = []
for _ in range(n):
s.append(input())
ans = []
for i in range(n):
for j in range(n):
if i != j:
ans.append(s[i]+s[j])
print(len(set(ans)))
C - Large Queue -
最初は空の整数列Aがあり、与えられたクエリを処理していく問題。与えられるクエリの入力と内容は以下です。
- 1 c x ：Aの末尾に値xをc個追加する。
- 2 k ：Aの先頭からk個の要素を削除し、削除した要素の合計値を出力する。
クエリの数は最大$2×10^5$、1回のクエリで追加したり削除したりする要素数は最大$10^9$です。クエリを正確に処理してリストをシミュレーションするようなコーディングはダメそうでした。
ということで、ざっくり説明ですが各クエリの処理を以下のようにしてみました。
- その時点のAの先頭を指すindexを用意する(最初は0)
- Aに要素を追加するときは[c,x]をAの末尾に追加する
- Aから要素をk個削除するとき、A[index]の[c,x]を[c-k,x]とし、k * xを出力する。もしc < kの場合はA[index+1]の[c',k']から不足分の要素数 * k'も加算した値を出力する。(以下、k個削除できるまでindexを増やしていく)
こんな感じで実装したのが以下です。ところで、リストの操作は追加のみとしindexで先頭位置を持つのが計算量削減に必要でした。最初の実装で要素が0になった[c,x]をpopで削除したんですがTLEになりました。
n = int(input())
s = []
index = 0
for _ in range(n):
q = [int(x) for x in input().split()]
if q[0] == 1:
s.append([q[1],q[2]])
else:
ans = 0
count = q[1]
while count > 0:
if s[index][0] >= count:
ans += count * s[index][1]
s[index][0] -= count
if s[index][0] == 0:
index += 1
count = 0
else:
ans += s[index][0] * s[index][1]
count -= s[index][0]
index += 1
print(ans)
--- 2025/7/9追記 ---
D - Make Geometric Sequence -
与えられた整数列を並び替えたら等比数列になるかを判定する問題。1回で最大$10^5$のテストケースが与えられ、整数列の最大要素数は$2×10^5$というところです。
コンテスト中は整数列をソートして比較すればよいということまではわかったんですが、正負の数が混在する場合の整列方法がわからず断念していました。
解説を見ると絶対値で整列すればよいと書いてあり得心がいったので、以下のアルゴリズムで実装してACとなりました。
- 整数列を絶対値で昇順にソート
- 公比で場合分けして以下のとおり判定
- 公比が-1：整数列の要素数が偶数なら正の値の要素数と負の値の要素数が一致するか判定。要素数が奇数なら正の値の要素数と負の値の要素数の差が1個か判定
- 公比が1 ：整数列の要素がすべて同じであるか判定
- それ以外：i番目の値とi+2番目の値の積がi+1番目の値の2乗と一致するか判定
t = int(input())
for _ in range(t):
n = int(input())
s = [int(x) for x in input().split()]
s.sort(key = lambda x : abs(x))
ans = True
if s.count(s[0]) + s.count(s[0] * -1) == len(s) and s.count(s[0] * -1) != 0:
if (len(s) % 2 == 0 and s.count(s[0]) != s.count(s[0] * -1)) \
or (len(s) % 2 == 1 and abs(s.count(s[0])-s.count(s[0] * -1)) != 1):
ans = False
elif s[0] == s[1]:
if s.count(s[0]) != len(s):
ans = False
else:
for i in range(n-2):
if s[i] * s[i+2] != s[i+1] ** 2:
ans = False
break
print("Yes" if ans else "No")
--- 追記ここまで ---
ではでは。