【AtCoder】初学者，TLEに心を折られる

はじめに

PythonでAtCoderにチャレンジしているのですが，TLEで挫折することが多々あります．
今回もそんな感じになったので，初記事を書いてみます．ちなみに，PythonもAtCoderもともにぺーぺーです．

発生している問題・エラー

例えば，タイムリーなこの問題（AtCoder Regular Contest 130 B- Colorful Lines）．後工程から見ていく方法でトライしました．

以下の通り回答しましたが．TLEが22/35となりました．平均2206msかかっている．
$Q ≤ 3×10^5$　でしたが，おそらくN, Mを毎ループ探してしまうのがダメなのか…しかしそれをしないやり方はあるのか…．

import sys
input = sys.stdin.readline

H, W, C, Q = map(int, input().split())
t = [0] * Q
n = [0] * Q
c = [0] * Q
for i in range(Q):
  t[i], n[i], c[i] = map(int, input().split())

N = []
M = []
ans = [0] * C
for i in range(Q)[::-1]:
  if t[i] == 1 and n[i] not in N:
    ans[c[i]-1] += W - len(M)
    N.append(n[i])  
  elif t[i] == 2 and n[i] not in M:
    ans[c[i]-1] += H - len(N)
    M.append(n[i])
  elif len(N) == H and len(M) == W:
    break

print(*ans)

自分で試したこと

此方を参考に，何度かトライをしました．

• PypyとPythonを行き来．
• input を sys.stdin.readline にすることで読込時間を1/10程度に短縮（できてる？せいぜい2ms程度しか縮まらなかった．）
• すべてのマスが埋まったらbreak（悪あがき）

whileではなくforを使っているし，あと変えられるところは…
という間に，やる気を失い，この記事の下書きを始めてしまいました．

答え合わせ

コンテスト終了後に公式解説を確認．全く同じ解き方で一安心．だが何が違うんだ．

一番効いていたのは，読込ではなく，埋まっている行・列（探索対象）をlistではなくset(集合)にすることでした．
これで計算時間は1/3～1/4程度に．

import sys
input = sys.stdin.readline

H, W, C, Q = map(int, input().split())
t = [0] * Q
n = [0] * Q
c = [0] * Q
for i in range(Q):
  t[i], n[i], c[i] = map(int, input().split())

# set(集合)をセット．
N = set()
M = set()
ans = [0] * C

for i in range(Q)[::-1]:
  if t[i] == 1 and n[i] not in N:
    ans[c[i]-1] += W - len(M)
    N.add(n[i]) # appendではなくadd．
  elif t[i] == 2 and n[i] not in M:
    ans[c[i]-1] += H - len(N)
    M.add(n[i])
  elif len(N) == H and len(M) == W:
    break

print(*ans)

基本的なことですが，setをもっと使おうと思います．

追記

• setがtupleになっていたものを修正しました．
• 参考になる記事を@snhrhdtさんに共有いただきました．「知らないと恥ずかしい」…