I had a feeling of refusal for the lie that the amount of calculation was O (1) (I think I understand the reason), and I have not used dict stubbornly until now, but at the FHC I participated in last week Easy problem with dict
When the range of values is large and sparse
Have elements in the form of key, value
Elements can be inserted, deleted, updated, and searched with O (1) [Reference: Wikipedia HashTable](https://ja.wikipedia.org/wiki/%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E3%83%86% E3% 83% BC% E3% 83% 96% E3% 83% AB)
| Operations that can be performed | code | comment |
|---|---|---|
| Declaration | b = {'one': 1, 'two': 2, 'three': 3} | a = dict(key1=value1,key2=value2,..)And various other writing styles |
| Element count | len(d) | |
| Value reference | d[key] | d[key]KeyError occurs when key does not exist |
| Value reference(Unknown if it exists) | d.setdefault(key,default) | Returns the value of key, if it exists in the dictionary. Otherwise, insert the key with the value default and return default |
| Add element | d[key] = value | Same for updates |
| Element update | d[key] = value | Same for addition |
| Delete element | del d[key] | If not, KeyError |
| Delete element(Unknown if it exists) | d.pop(key,default) | If not, return default |
| Search for elements | key in d | |
| Search for elements(When you want to use value) | d.get(key,default) | Returns the value corresponding to key. Returns default if key does not exist |
| Delete all elements of the dictionary | clear() | |
| Take out in the reverse order of insertion | d.popitem() | |
| Reversal of order | reversed(d) | |
| List | list(d.items()) | Returns as a list of tuples |
| List(key,value only) | list(d.keys()) | |
| loop(key,value) | d.items() | key,value is returned as a tuple |
| loop(key,value Only one) | d.keys() or d.values() |
dict.py
>>>dic = dict(a=1,b=2,c=3)
#Even if it is a character string""Write as it is without attaching
>>> dic
{'a': 1, 'b': 2, 'c': 3}
#However, attach it when referring to it
>>> 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}
#It is also possible to define with this writing style
>>> dic.clear()
>>> dic
{}
>>> dic = {1:1,2:1,3:2,4:3,5:5}
#key can be a numerical value
>>> 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)]
#If you want to loop elements
>>> for k,v in dic.items():
... print(k,v)
...
1 8
2 1
3 2
4 3
5 5
Since it is a big deal, I will solve the FHC problem introduced at the beginning using dict. If you are interested in the problem itself, please try Commentary I wrote.
This time, except for declaration and assignment, I used only value reference with get and loop with items (), but I was able to write sparse dp easily. It was a difference from having idx in the binary search, so I would like to continue using it in the future.
timer.py
import bisect
import sys
read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
# step1:Sit down (in sorted order))Perform DP from both the left and right edges
# dp_l[i] = max(dp_l[j] + h[i],h[i])Tree leading to place i(i=j+h[j])Search by dict
# dp_r[i] = max(dp_r[j] + h[i],h[i])
# step2:dp_l_For all key i in dict, dp_r_Find out if it is in the dict key with dict(p[i]+h[i]Is p[j]-h[j]Becomes j i,Equivalent to looking for j)
# step3:Matching in step2 i,for 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)))
#In ascending order with p, sort to the right, see in ascending order, and to the left, see in descending order.
#Looking from the left To what you see from the left
#dp has key as pos,value puts in length
dp_r_dict = {} #Pos ends in a row of trees that fall to the right(Right end) The longest length in the column
dp_l_dict = {}
for i in range(n):
# dict[p[i]]If there is, it returns it, otherwise it returns 0
#If p[i]If there is something that ends with, you can connect it and stretch it
tmp = dp_l_dict.get(p[i], 0) + h[i]
if dp_l_dict.get(p[i] + h[i], 0) < tmp: #Similarly
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_For dict, dp with all keys_r_Check if there is a match with the key of dict and take max
ans = 0
for pos, l_len in dp_l_dict.items():
tmp = l_len + dp_r_dict.get(pos, 0) #All can be facing right
ans = max(ans, tmp)
#Consider all leftward
ans = max(ans, r_max)
case_str = "Case #" + str(case + 1) + ": " + str(ans)
print(case_str)
Please comment if you have any mistakes or better writing.
Recommended Posts