【TLE】C - Variety

回答

N, K, M = list(map(int, input().split()))
l = [list(map(int, input().split())) for l in range(N)]
result=0
clrv=[]
li = sorted(l, reverse=True, key=lambda x: x[1])
k=[]
v=[]
isPrinted=False
for i in range(len(li)):
  if K-len(k) == 0:
    print(sum(v))
    isPrinted=True
    break
  if (K-len(k) > M-len(set(k))):
    k.append(li[i][0])
    v.append(li[i][1])
  elif (li[i][0] not in k):
    k.append(li[i][0])
    v.append(li[i][1])
if (isPrinted==False):
  print(sum(v))

振り返り

おそらく宝石の数が大量の場合にTLEになっている。ハッシュマップを使うなど線形探索以外の方法を模索したい。
日を跨いで問題を解き直してみる、数学の真似をして問題を単純化→単純化したものを抽象化など問題を変形させる考え方をしたのは、よかった点だと思う

メモ

N, K, M = list(map(int, input().split()))
l = [list(map(int, input().split())) for l in range(N)]
result=0
clrv=[]
# 価値が大きい順にソート
li = sorted(l, reverse=True, key=lambda x: x[1])
k=[]
v=[]
isPrinted=False

for i in range(len(li)):
  if K-len(k) == 0:
    print(sum(v))
    isPrinted=True
    break

  # 取る数が、取る種類に対してあまりがあったら。と、
  if (K-len(k) > M-len(set(k))):
    # print("")
    k.append(li[i][0])
    v.append(li[i][1])
  elif (li[i][0] not in k):
    k.append(li[i][0])
    v.append(li[i][1])
  # print(v)
  # print(k)
  # print(f"あと{K-len(k)}個")
  # print(f"あと{M-len(set(k))}種類")
  # print("")
if (isPrinted==False):
  print(sum(v))
  
  
  
# clrvにすでにあるものなら見ないにすれば良い
# likeys=[]
# for i in range(len(li)):
#   if(li[i][0] not in likeys):
#     likeys.append(li[i][0])
# likeyss=sorted(likeys, reverse=True)
# wthlikeyidx=0
# for i in range(len(li)):
#   if (li[i][0] == likeyss[wthlikeyidx]):
#     print(f"li[i][0]: {li[i][0]}")
#     print(f"li[i][1]: {li[i][1]}")
#     print(f"===")  
  # まだ同じ色の宝石を選べるのであれば一番大きいものを入れる。
  # if (M-len(clrv) < K-len(clrv)):
  #   print(f"とらないといけない残種類数: {M-len(clrv)}")
  #   print(f"　　　　　　　　とれる個数: {K-len(clrv)}")
  #   print(clrv)
  #   print("===")
  #   if (li[i][0] not in clrv):
  #     clrv.append(li[i][0])
  #     result+=li[i][1]
  # 同じ色を選べない場合はまだ選んでいない色で一番大きいものを入れる
  # elif (len(clrv) < K-len(clrv) and li[i][0] not in clrv):
    # clrv.append(li[i][0])
    # result+=li[i][1]
    # print("elif")
# print(result)

# for i in range(len(li)):
#   if (M-len(clrv) < K-len(clrv) and li[i][0] not in clrv): 
    # print(f"li[i][0]: {li[i][0]}")
    # print(f"li[i][1]: {li[i][1]}")
    # print(f"とらないといけない残種類数: {M-len(clrv)}")
    # print(f"　　　　　　　　とれる個数: {K-len(clrv)}")
    # print(f"===")
#     clrv.append(li[i][0])
#     result+=li[i][1]
#   elif():
# print(result)

# print(f"N: {N}")
# print(f"K: {K}")
# print(f"M: {M}")
# print(f"l: {l}")
# print(f"li: {li}")