💨
[Python] ABC397 C Variety Split Easy
ABC397 C Variety Split Easy (Python)
目的
- コンテスト中に私自身が回答できなかった問題について、振り返り、理解を深めるための記事です。
- 初心者のため誤解している部分も多いかと思いますが、理解不足の点はその旨記載しています。
問題
自分の回答
-
maeに一旦全部リストの中身を詰めて、pop()でリストの後ろから取り出し、setの長さを見ることで組み合わせ数を確認する - 結果はTLE。listの長さ分
pop()を繰り返したり、前半のsetから削除していいかどうか判断する部分で時間が掛かっていると思う。
n = int(input())
A = list(map(int,input().split()))
mae = set(A)
usiro = set()
ans = 0
for i in range(n-1):
base = A.pop(-1)
usiro.add(base)
if(base not in A):
mae.discard(base)
# print(mae,usiro)
m = len(mae)
u = len(usiro)
if(m+u > ans):
ans = m+u
print(ans)
どうすればよかったのか
-
直接リストを操作して回答しようとするのではなく、特定のiで分割したときの組み合わせ数を保持しておき、最後に足し算する
-
入力1を例にすると、以下の通り
-
前半部分は以下
- i = 1 / (3) なので、1種類
- i = 2 / (3,1) なので、2種類
- i = 3 / (3,1,4) なので、3種類
- i = 4 / (3,1,4,1) なので、3種類
-
これらを、前半の組み合わせリストとして保持する
- [1,2,3,3]
-
同じように後半部分も考える
- i = 1 / (1,4,1,51) なので、3種類
- i = 2 / (4,1,5) なので、3種類
- i = 3 / (1,5) なので、2種類
- i = 4 / (5) なので、1種類
-
これらを後半の組み合わせリストとして保持する
- [3,3,2,1]
-
区切りがiの際に前半/後半にそれぞれ何種類の数字が含まれるかのリストが作れたので、それぞれ足し算することで答えが求められる
-
n = int(input())
A = list(map(int,input().split()))
# 前半のリストを作る
mae = []
mae_set = set()
for i in range(n-1):
mae_set.add(A[i])
mae.append(len(mae_set))
# 後半のリストを作る
usiro = []
usiro_set = set()
# 後ろから見たいので反転
A.reverse()
for i in range(n-1):
usiro_set.add(A[i])
usiro.append(len(usiro_set))
# 後ろのリストも逆転
usiro.reverse()
# 前半、後半のリストができたので足し算する
ans = 0
for i in range(n-1):
ans = max(ans,mae[i] + usiro[i])
print(ans)
補足
- 後半部分のリストを作るところはsortなしで出来る(現在の理解度だと思い付かなかった)
- 公式の解説や他の方の解説を見ると、事前にn-1の長さの配列を用意しておいて、そこに前半/後半の種類数を埋めていく方式みたい。
- 以下、入力1を例にする
- 事前に以下の配列を用意
- 前半用の配列 [0,0,0,0]
- 後半用の配列 [0,0,0,0]
- 前半、後半それぞれ詰めてゆく
# 前半のリストを作る mae = [0] * (n-1) mae_set = set() for i in range(n-1): mae_set.add(A[i]) mae[i] = len(mae_set) # 後半のリストを作る usiro = [0] * (n-1) usiro_set = set() for i in range(n-1,0,-1): usiro_set.add(A[i]) usiro[i-1] = len(usiro_set) - 事前に以下の配列を用意
- おそらくこちらの方が計算量的に優位なのか、実行時間が早くなった(要勉強)
Discussion