set と辞書で「見たこと」を記録

同じ値があるかを毎回すべて探す必要はありません。set は重複を除き、dict は値と情報を対応付けます。

言語：Python / 計算量：平均 O(N)

前提：ソートで順序を作る

考え方

  1. set(a) は異なる値の集合。
  2. x in seen で存在を調べます。
  3. Counter は値ごとの出現回数を数えます。

具体例

[2,2,5,2] の集合は {2,5}。Counter では2が3回、5が1回です。

実装

from collections import Counter
a = [2, 2, 5, 2]
c = Counter(a)
print(c[2])

注意する条件

集合の順序には頼らないでください。ハッシュ操作の O(1) は平均的な見積もりです。

確認問題

len(set([1,1,2,4,4])) は？

解答と理由

3

異なる値は1,2,4です。

実装課題

N と配列 A が2行。異なる値の種類数を求める。1 ≤ N ≤ 200000、|A_i| ≤ 10^9。

入力:
5
1 1 2 4 4
出力:
3
参考実装
n = int(input())
a = list(map(int, input().split()))
print(len(set(a)))

実戦につなげる補講

一度に全て読まなくて大丈夫です。今日は1節と1問から。

setと辞書は、質問に合わせて選ぶ

あるかないかだけならset。何個あるかなら辞書またはCounter。元の位置も必要なら値から位置のリストへの辞書を作ります。保存する情報を削りすぎると後から答えられません。

構築をループの外へ出す

毎回x in set(a)と書くと、質問ごとに集合を作り直します。s=set(a)を1回だけ実行してから質問します。平均で前処理O(N)、Q回の検索O(Q)。追加メモリは異なる値の数に比例します。

先に問い合わせ、あとで登録

右から新しい値xを読むとき、辞書に入っているのは過去の要素だけ、と決めます。これが不変条件です。target−xの個数を足してからxを登録すると、1組は右側の要素を読むときだけ数えられます。

段階式の追加演習

1. 集合で失う情報

a=[3,3,3,9]をsetにしたあと、3が何個だったか分かる？

ヒント

集合が保持するのは種類。

解答と理由

分からない。個数が必要ならCounter(a)や辞書で回数を保存する。

2. 構築コストの罠

Q個の質問に、毎回x in set(a)で答える。平均の計算量は？

ヒント

set(a)をいつ実行するか。

解答と理由

O(NQ)。集合を1回だけ作れば平均O(N+Q)。

3. 実装：過去の個数で組を数える

全探索のcount_pairsを、辞書で高速化して。重複する値があっても添字の組数を答える。

ヒント

seen.get(target-x,0)を足したあとseen[x]を増やす。

解答と理由

平均O(N)、メモリO(N)。同じ要素を2回使わない理由は、辞書には過去の要素だけがあるため。

def count_pairs(a, target):
    seen = {}
    answer = 0
    for x in a:
        answer += seen.get(target - x, 0)
        seen[x] = seen.get(x, 0) + 1
    return answer

4. 手で追って反例を探す

a=[4,4,4],target=8。前のコードでanswerはどう変化する？ 登録を先にすると？

ヒント

読む前の4の個数は0,1,2。

解答と理由

正しい順序なら0→1→3。登録が先だと自分自身も数えて1→3→6になり誤り。

公式過去問への橋渡し

ABC248 D / 公式解説

値ごとの出現位置を保存し、区間の境界を二分探索する。前処理と質問処理を分けて数える。

公式問題 / 公式解説

見本を閉じて確認

読了の記録・下書き・メモへ