計算量がO(1)という嘘んくささ（一応理由は理解しているつもりですが）に拒否感があり、今まで頑なにdictを使ってきていなかったのですが、先週参加したFHCでdictを使うと楽な問題が出たのでメモ
使うタイミング
値をとる範囲が大きく、sparse な時
行える操作
key, value の形で要素を持つ
要素の挿入、削除、更新、検索がO(1)で行える
参考:Wikipedia HashTable
よく使う操作
| 行える操作 | コード | コメント |
|---|---|---|
| 宣言 | b = {'one': 1, 'two': 2, 'three': 3} | a = dict(key1=value1,key2=value2,..) などその他いろいろな書き方 |
| 要素数 | len(d) | |
| 値の参照 | d[key] | d[key]keyが存在しない時KeyErrorになる |
| 値の参照(存在するか不明) | d.setdefault(key,default) | key が辞書に存在すれば、その値を返します。そうでなければ、値を default として key を挿入し、 default を返します |
| 要素の追加 | d[key] = value | 更新も同じ |
| 要素の更新 | d[key] = value | 追加も同じ |
| 要素の削除 | del d[key] | なければKeyError |
| 要素の削除(存在するか不明) | d.pop(key,default) | なければdefaultを返す |
| 要素の検索 | key in d | |
| 要素の検索(valueを使いたい時) | d.get(key,default) | key に対応するvalueを返す。key が存在しなければdefaultを返す |
| 辞書の全ての要素の削除 | clear() | |
| 挿入した順番の逆順に取り出し | d.popitem() | |
| 順序の反転 | reversed(d) | |
| リスト化 | list(d.items()) | タプルのリストとして返る |
| リスト化(key,valueのみ) | list(d.keys()) | |
| ループ(key,value) | d.items() | key,valueがタプルで返る |
| ループ(key,value片方のみ) | d.keys() or d.values() |
例
dict.py
>>>dic = dict(a=1,b=2,c=3)
# 文字列の場合でも"" などつけずそのまま書く
>>> dic
{'a': 1, 'b': 2, 'c': 3}
# ただし参照する時はつける
>>> dic[a]
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'dict'
>>> dic["a"]
1
>>> dic.pop("a")
1
>>> dic
{'b': 2, 'c': 3}
# この書き方で定義することも可能
>>> dic.clear()
>>> dic
{}
>>> dic = {1:1,2:1,3:2,4:3,5:5}
# key は数値でもOK
>>> dic[1]
1
>>> dic[1]=8
>>> dic
{1: 8, 2: 1, 3: 2, 4: 3, 5: 5}
>>> dic.get(1,-1)
8
>>> list(dic.keys())
[1, 2, 3, 4, 5]
>>> list(dic.values())
[8, 1, 2, 3, 5]
>>> list(dic.items())
[(1, 8), (2, 1), (3, 2), (4, 3), (5, 5)]
# 要素をループしたい場合
>>> for k,v in dic.items():
... print(k,v)
...
1 8
2 1
3 2
4 3
5 5
競プロの問題での利用
せっかくなので、冒頭で紹介したFHCの問題をdictを使って解きます。
問題自体に興味のある方は僕が書いた解説なんかもよかったらみてください
今回は宣言、代入の他はgetでの値の参照,items()でのループくらいしか使っていませんが、sparse なdp を簡単に書くことができました。二分探索でidxを持ちつつやったのとは雲泥の違いだったので今後も使っていきたいものです。
timer.py
import bisect
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
# step1:座圧して（ソートした順番で)DPを左端と右端両方から行う
# dp_l[i] = max(dp_l[j] + h[i],h[i]) 場所iにつながる木(i=j+h[j]) をdictで探す
# dp_r[i] = max(dp_r[j] + h[i],h[i])
# step2:dp_l_dictの全てのkey i に対して、dp_r_dictのkeyにあるかをdictで探す(p[i]+h[i] がp[j]-h[j]となるj i,j を探すのと同値)
# step3:step2で一致するi,jに対して、ans = max(ans,dp_l[i]+dp_r[j])
t = int(input())
for case in range(t):
n = int(input())
p = [0] * n
h = [0] * n
for i in range(n):
p[i], h[i] = map(int, input().split())
p, h = zip(*sorted(zip(p, h)))
# p で昇順にsort 右に倒すものは昇順に、左に倒すものは降順に見る
# 左から順番にみていく 左から見たものに
# dp はkey がpos,value が長さ で置く
dp_r_dict = {} # 右に倒れる木の列のなかでpos が末端(右端）列の中で最長の長さ
dp_l_dict = {}
for i in range(n):
# dict[p[i]]があればそれを返し、なければ0を返す
# もしp[i]で終わるものがあればそれをつなげて伸ばすことができるため
tmp = dp_l_dict.get(p[i], 0) + h[i]
if dp_l_dict.get(p[i] + h[i], 0) < tmp: # 同様
dp_l_dict[p[i] + h[i]] = tmp
r_max = 0
for i in range(n - 1, -1, -1):
tmp = dp_r_dict.get(p[i], 0) + h[i]
if dp_r_dict.get(p[i] - h[i], 0) < tmp:
dp_r_dict[p[i] - h[i]] = tmp
r_max = max(r_max, dp_r_dict[p[i] - h[i]])
# step3:dp_l_dict に対して、全てのkey でdp_r_dictのkey と一致するのがあるかを調べmaxをとる
ans = 0
for pos, l_len in dp_l_dict.items():
tmp = l_len + dp_r_dict.get(pos, 0) # 全て右向きでもOK
ans = max(ans, tmp)
# 全て左向きを考慮する
ans = max(ans, r_max)
case_str = "Case #" + str(case + 1) + ": " + str(ans)
print(case_str)
終わりに
間違いやもっと良い書き方等ありましたらコメントください。