AtCoder Beginner Contest 413 を解いてみました
今回はリアルタイム参加できなかったため、後日時間を取って問題を解いてみました。結果は、約90分でABCDまで4問解けました(ただし、D問題で4回WA)。
A - Content Too Large
sum(A) で配列の合計値が求められるので、それと M を比較します。
N, M = map(int, input().split())
A = list(map(int, input().split()))
# 配列Aの合計値を M と比較
sumA = sum(A)
print("Yes" if sumA <= M else "No")
B - cat 2
合成した文字列を set に入れることで、重複を取り除くことが出来ます。ちょっと無駄が多いループですが、Nが小さいので制限時間には間に合います。
N = int(input())
S = []
for i in range(N):
S.append(input())
# 重複しないようにsetで集計する
str_set = set()
# 合成文字列を作成する
for i in range(N):
for j in range(N):
# 同じSのときは合成しない
if i == j:
continue
str_set.add(S[i] + S[j])
print(len(str_set))
C - Large Queue
末尾に数字を追加し、先頭から数字を取り出す...ということで、両面キュー(deque)を使用します。
「5 を 4 個追加する」操作をしたい場合、[5 5 5 5] と素直に追加すると、実行時間がかかってTLEになります。
そこで、[(4, 5)] のようにタプルをキューに追加する方法を採用しました。
こうすることで、例えば「2を1000個追加する」を[(1000, 2)] と1回のキューへの追加で済ませることができます。
取り出すときも同様に、例えば 「[(1000, 2)] から500個取り出す」操作を、[(500, 2)] に変えるだけで実現できます。
from collections import deque
# 両面キュー
que = deque()
Q = int(input())
for i in range(Q):
query = list(map(int, input().split()))
if query[0] == 1:
# 1 のときは末尾に追加
c = query[1]
x = query[2]
que.append((c, x))
else:
# 2のときは k個の数字を先頭から取り出す
k = query[1]
answer = 0
while k > 0 and que:
c, x = que.popleft()
if c <= k:
# c個取り出しても、更に取り出せるとき
k -= c
answer += c * x
else:
# k個取り出し終えたとき
que.appendleft((c - k, x))
answer += k * x
k = 0
print(answer)
D - Make Geometric Sequence
4回間違えました。復習して、難なく解けるようになってみたいものです。
Aに含まれる数字が1種類のとき
このときは、必ず等比数列になります。
例 [2 2 2 2 2] は、初項2公比1の等比数列
Aに含まれる数字が2種類のとき
以下の条件を満たせば、等比数列になります。
- 2種類の数字が お互いに -1 をかけたものである
- Aの個数が偶数のとき、2種類の数が同数あればよい
- 例 [2 -2 2 -2] (公比-1の等比数列)
- Aの個数が奇数のとき、2種類の数の個数の差が1であればよい
- 例 [2 -2 2 -2 2] または [-2 2 -2 2 -2]
Aに含まれる数字が3種類以上のとき
配列Aを、絶対値でソートして考えます。
A=[1 -8 -2 4 16] (絶対値でソート)-> A=[1 -2 4 -8 16]
A[1]/A[0] の比率が A[2]/A[1], A[3]/A[2], A[4]/A[3] の比率とすべて一致していれば、等比数列になります。
コンピューターの性質として、割り算をして小数になってしまうと、正確な比較ができません。そこで、以下のように式変形して、小数を使わないようにしました。
A[1] / A[0] == A[i] / A[i-1] # 小数のため誤差が出てしまう
↓
A[1] * A[i-1] == A[0] * A[i] # 小数が出ないように判定
from collections import defaultdict
# Aが等比数列かどうかを判定するメソッド
def is_correct(A):
if len(A) == 2:
return True
value_dict = defaultdict(int)
abs_a = []
for a in A:
if a < 0:
abs_a.append((-a, -1))
value_dict[a] += 1
else:
abs_a.append((a, 1))
value_dict[a] += 1
# Aが1種類のときは等比数列(公比1の)
if len(value_dict) == 1:
return True
# Aが2種類のときは、公比−1 の等比数列しかありえない
if len(value_dict) == 2:
keys = list(value_dict.keys())
key1 = keys[0]
key2 = keys[1]
# 公比−1になりえるかどうか
if key1 != key2 * -1:
return False
# Aの個数が偶数 → 2つの数字の個数が同じなら、公比-1の等比数列
if len(A) % 2 == 0 and value_dict[key1] == value_dict[key2]:
return True
# Aの個数が奇数 → 2つの数字の個数の差が1なら、等比数列
if len(A) % 2 == 1 and ((value_dict[key1] == value_dict[key2] + 1) or (value_dict[key1] + 1 == value_dict[key2])):
return True
return False
abs_a.sort()
# Aが3種類以上のとき → 各項をチェック
is_correct = True
for i in range(1, len(abs_a)):
# チェック： A[i] * A[0] == A[i-1] * A[1] なら等比数列
if abs_a[i][0] * abs_a[i][1] * abs_a[0][0] * abs_a[0][1] == abs_a[i - 1][0] * abs_a[i - 1][1] * abs_a[1][0] * abs_a[1][1]:
continue
else:
is_correct = False
break
return is_correct
# 各テストケースを調べる
T = int(input())
for _ in range(T):
N = int(input())
A = list(map(int, input().split()))
if is_correct(A):
print("Yes")
else:
print("No")