Remarques sur l'utilisation de dict avec python [Competition Pro]

J'avais un sentiment de refus pour le menteur que le montant du calcul est O (1) (je pense que je comprends la raison), et je n'ai pas utilisé dict obstinément jusqu'à présent, mais au FHC j'ai participé la semaine dernière Problème facile avec dict

Délai d'utilisation

Lorsque la plage de valeurs est large et clairsemée

Opérations pouvant être effectuées

Avoir des éléments sous forme de clé, de valeur

Les éléments peuvent être insérés, supprimés, mis à jour et recherchés avec O (1) [Référence: 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)

Opérations fréquemment utilisées

Opérations pouvant être effectuées code commentaire
Déclaration b = {'one': 1, 'two': 2, 'three': 3} a = dict(key1=value1,key2=value2,..)Et divers autres styles d'écriture
Nombre d'éléments len(d)
Référence de valeur d[key] d[key]KeyError se produit lorsque la clé n'existe pas
Référence de valeur(Inconnu s'il existe) d.setdefault(key,default) Renvoie la valeur de la clé, si elle existe dans le dictionnaire. Sinon, insérez la clé avec la valeur par défaut et renvoyez la valeur par défaut
Ajouter un élément d[key] = value Idem pour les mises à jour
Mise à jour des éléments d[key] = value Idem pour l'ajout
Supprimer l'élément del d[key] Sinon, KeyError
Supprimer l'élément(Inconnu s'il existe) d.pop(key,default) Sinon, retournez par défaut
Rechercher des éléments key in d
Rechercher des éléments(Quand vous voulez utiliser de la valeur) d.get(key,default) Renvoie la valeur correspondant à la clé. Renvoie la valeur par défaut si la clé n'existe pas
Supprimer tous les éléments du dictionnaire clear()
Sortez dans l'ordre inverse de l'insertion d.popitem()
Annulation de commande reversed(d)
liste list(d.items()) Renvoie sous forme de liste de taples
liste(key,valeur seulement) list(d.keys())
boucle(key,value) d.items() key,la valeur revient sous forme de taple
boucle(key,valeur Un seul) d.keys() or d.values()

Exemple

dict.py


>>>dic = dict(a=1,b=2,c=3)
#Même s'il s'agit d'une chaîne de caractères""Écrivez tel quel sans attacher
>>> dic
{'a': 1, 'b': 2, 'c': 3}
#Cependant, attachez-le en vous y référant
>>> 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}
#Il est également possible de définir de cette manière d'écrire
>>> dic.clear()
>>> dic
{}
>>> dic = {1:1,2:1,3:2,4:3,5:5}
#la clé peut être une valeur numérique
>>> 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)]
#Si vous voulez boucler des éléments
>>> for k,v in dic.items():
...     print(k,v)
...
1 8
2 1
3 2
4 3
5 5

Utilisation dans les problèmes professionnels de la concurrence

Comme c'est un gros problème, je vais résoudre le problème FHC introduit au début en utilisant dict. Si vous êtes intéressé par le problème lui-même, veuillez essayer Explication que j'ai écrite.

Cette fois, à l'exception de la déclaration et de l'affectation, j'ai utilisé uniquement la référence de valeur avec get et loop avec items (), mais j'ai pu écrire facilement des dp épars. C'était une différence d'avoir idx dans la dichotomie, alors j'aimerais continuer à l'utiliser à l'avenir.

timer.py


import bisect
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# step1:Asseyez-vous (dans l'ordre trié))Effectuer DP à partir des bords gauche et droit
# dp_l[i] = max(dp_l[j] + h[i],h[i])Arbre menant à la place i(i=j+h[j])Recherche par dict
# dp_r[i] = max(dp_r[j] + h[i],h[i]) 
# step2:dp_l_Pour toutes les clés i dans dict, dp_r_Découvrez si c'est dans la clé de dict avec dict(p[i]+h[i]Est p[j]-h[j]Devient j i,Équivaut à rechercher j)
# step3:Correspondance à l'étape 2 i,pour 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)))
    #Dans l'ordre croissant avec p, voyez dans l'ordre croissant pour ceux qui sont poussés vers la droite, et dans l'ordre décroissant pour ceux qui sont poussés vers la gauche.

    #En regardant de gauche à ce que vous voyez de gauche
    #dp a la clé comme pos,la valeur met en longueur
    dp_r_dict = {}  #Pos se termine par une rangée d'arbres qui tombent à droite(Extrémité droite) La plus longue longueur de la colonne
    dp_l_dict = {}
    for i in range(n):
        # dict[p[i]]S'il y en a, il le renvoie, sinon il retourne 0
        #Si p[i]S'il y a quelque chose qui se termine par, vous pouvez le connecter et l'étirer
        tmp = dp_l_dict.get(p[i], 0) + h[i]
        if dp_l_dict.get(p[i] + h[i], 0) < tmp:  #De même
            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_Pour dict, dp avec toutes les touches_r_Vérifiez s'il y a une correspondance avec la clé de dict et prenez max
    ans = 0
    for pos, l_len in dp_l_dict.items():
        tmp = l_len + dp_r_dict.get(pos, 0)  #Tout peut être face à la droite
        ans = max(ans, tmp)
    #Considérez tout vers la gauche
    ans = max(ans, r_max)
    case_str = "Case #" + str(case + 1) + ": " + str(ans)
    print(case_str)

À la fin

Veuillez commenter si vous avez des erreurs ou une meilleure écriture.

référence

python Document

Recommended Posts

Remarques sur l'utilisation de dict avec python [Competition Pro]
Remarques sur l'utilisation de MeCab depuis Python
Remarques sur l'installation de Python à l'aide de PyEnv
Notes sur l'utilisation de rstrip avec python.
Remarques sur l'utilisation d'OpenCV avec Windows10 Python 3.8.3.
Notes utilisant cChardet et python3-chardet dans Python 3.3.1.
Remarques sur l'utilisation de python (pydev) avec eclipse
Remarques sur l'installation de Python3 et l'utilisation de pip sous Windows7
ABC125_C --GCD sur tableau noir [Notes résolues en Python]
Notes sur l'utilisation de sous-processus Python
Remarques sur l'utilisation d'Alembic
[Python] Remarques sur l'accélération des algorithmes génétiques à l'aide du multitraitement
Notes minimales lors de l'utilisation de Python sur Mac (édition Homebrew)
mémo python utilisant l'opérateur perl-ternaire
notes python pour l'utilisation de variables spéciales perl
[Django] Remarques sur l'utilisation de django-debug-toolbar
Entrée standard Python3 (compétition pro)
Utiliser un dict clé de liste en Python
[Python] Notes sur l'analyse des données
Remarques sur l'optimisation à l'aide de Pytorch
Remarques sur l'installation de Python sur votre Mac
Diffusion sur LINE en utilisant python
Obtenez des notes Evernote en Python
Remarques sur imshow () d'OpenCV
Traduit à l'aide de googletrans en Python
Remarques sur l'installation de Python sur CentOS
Utilisation du mode Python dans le traitement
Notes sur la lecture et l'écriture d'images TIFF float32 avec python
Programmation GUI en Python avec Appjar
Notes sur Python et les types de dictionnaire
Précautions lors de l'utilisation de Pit avec Python
Remarques sur l'utilisation de la post-réception et de la post-fusion
Essayez d'utiliser LevelDB avec Python (plyvel)
Utilisation de variables globales dans les fonctions python
Étude sur Tokyo Rent en utilisant Python (3-2)
Voyons voir l'utilisation de l'entrée en python
Puissance totale en Python (en utilisant functools)
Remarques sur l'accès à dashDB à partir de python
Installer Python sur CentOS à l'aide de Pyenv
Étude sur Tokyo Rent en utilisant Python (3-3)
Reconnaissance de caractères manuscrits à l'aide de KNN en Python
Remarques sur l'utilisation de matplotlib sur le serveur
Essayez d'utiliser LeapMotion avec Python
Recherche de priorité de profondeur à l'aide de la pile en Python
Installez Python sur CentOS en utilisant pyenv
Lors de l'utilisation d'expressions régulières en Python
(Débutant) Remarques sur l'utilisation de pyenv sur Mac
Création d'interface graphique en python avec tkinter 2
Essayez de vous connecter automatiquement à Netflix en utilisant python sur votre PC
Résumé de l'entrée standard de Python pouvant être utilisée dans Competition Pro
Fonctionnement de la souris à l'aide de l'API Windows en Python
Essayez d'utiliser l'API Wunderlist en Python
Création d'interface graphique en python à l'aide de tkinter partie 1
Exécuter du code Python sur C ++ (en utilisant Boost.Python)
Obtenir l'équilibre Suica en Python (en utilisant libpafe)