ABC170 E - Comment résoudre sans utiliser le multiset de Smart Infants

L'explication utilisant multiset a été écrite dans le problème E d'AtCoder Beginner Contest, mais je pense qu'il existe des langages tels que python qui n'ont pas de mutiset, je voudrais donc introduire un algorithme alternatif utilisant Priority Queue (heapq). Je n'expliquerai pas le problème lui-même, alors veuillez lire l'explication officielle ici.

problème

ABC170 E - Smart Infants https://atcoder.jp/contests/abc170/tasks/abc170_e

Connaissances préalables

multiset En interne [Arbre de dichotomie](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%8E%A2%E7%B4%A2%E6%9C % A8) est utilisé. Cela maintient les données triées à tout moment au lieu de prendre O (logN) chaque fois qu'une donnée est insérée. Par conséquent, il est possible de supprimer et de rechercher avec O (logN). En implémentant vous-même l'arbre de dichotomie, vous pouvez l'utiliser dans des langues qui ne sont pas fournies en standard, mais vous devez concevoir pour maintenir l'équilibre. (Exemple d'ingéniosité: [Formation de maître bois] 7-1. Qu'est-ce que le bois Splay? Explication [Compétition professionnelle Katsuppa])

Priority Queue En interne dans GCC [Dichotomy](https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83 % 97) est utilisé. La même structure de données est utilisée en interne dans heapq de python. L'insertion de données prend O (logN) à chaque fois, comme l'arbre de dichotomie. Puisqu'il s'agit d'un arbre de tas, l'intérieur n'est ** pas trié, et vous ne pouvez pas rechercher ou supprimer autre chose que la valeur maximale (minimale) à grande vitesse **, mais vous ne pouvez pas toujours obtenir la valeur maximale (minimale) avec le montant de calcul O (1). Je peux le faire. L'avantage par rapport à l'arbre de dichotomie est que la quantité de calcul est stable car l'équilibre est toujours maintenu sans aucune ingéniosité particulière.

Solution

Le point

Dans ce problème

  1. Obtenez le taux maximum dans chaque jardin d'enfants

Ce serait bien si cela pouvait toujours être fait à grande vitesse.

Comme mentionné dans le commentaire officiel, chaque processus peut être exécuté à grande vitesse en utilisant le multiset, mais comme le 4ème processus ne peut pas être exécuté à grande vitesse avec Priority Queue, il est nécessaire de changer la façon de penser.

En résolvant ce problème, notons que la quatrième condition n'est ** pas nécessairement un processus qui doit être exécuté à moins qu'il n'interfère avec les première et deuxième conditions **. En d'autres termes, même si elle n'est pas réellement supprimée des données, peu importe si la valeur maximale du taux fixé et la valeur minimale du taux maximal fixé dans chaque jardin d'enfants ne sont pas affectées.

Algorithme spécifique

Puisque l'implémentation ne change pas dans les première et seconde conditions (le maximum et le minimum sont retournés), la première condition (obtenir la valeur maximum de l'ensemble) sera expliquée à titre d'exemple.

Pensez maintenant à avoir deux files d'attente prioritaires.

  1. Ceux qui gèrent l'ensemble du jeu
  2. Celui qui contient l'élément qui aurait dû être supprimé

Et ** insérez un élément en 1 lorsque vous entrez dans le parc et en 2 lorsque vous changez de parc. Si les maximums de 1 et 2 sont identiques, supprimez-les des deux. ** ** Cela garantit que la valeur maximale pour ce jardin d'enfants est toujours la même que la valeur maximale pour 1.

Je vais mettre du code ici, mais cela ne fonctionne pas même si je le copie en fonction de l'environnement car std et include sont cassés.

code.cpp


priority_queue<int> in;
priority_queue<int> out;

//Traitement lors de l'entrée dans le parc
void infant_in(int i){
    in.push(i);
}

//Traitement lors du changement de jardin
void infant_out(int i){
    out.push(i);
    while(!out.empty() && in.top() == out.top()){
        in.pop();
        out.pop();
    }
}

//Obtenez le maximum
int get_max(){
    return in.top();
}

Regardons un exemple concret. Considérez que les enfants avec un taux de 3,5,8 entrent à la maternelle, puis les enfants avec un taux de 5,8 se déplacent dans cet ordre.


>Trois enfants de la maternelle entrent
Maternelle réelle= {3,5,8}
1 = [3,5,8] 2 = []   #Bien sûr, la valeur maximale à ce stade est de 8

>Les enfants avec un tarif de 5 sont transférés
Maternelle réelle= {3,8}
1 = [3,5,8] 2 = [5]  #La valeur maximale est 8

>Les enfants avec un tarif de 8 sont transférés
Maternelle réelle= {3}
1 = [3,5,8] 2 = [5,8]
1 = [3,5]   2 = [5]
1 = [3]     2 = []   #La valeur maximale est 3

Avec ce genre de sentiment, vous pouvez voir qu'il n'y a aucun problème à obtenir la valeur maximale.

Montant du calcul

C'est un montant de calcul dont il faut s'inquiéter, mais comme le nombre de fois pour supprimer la valeur d'entrée et de sortie qui semble être un goulot d'étranglement dans ce problème est Q fois au maximum, il peut être ignoré et le montant du calcul est O (NlogN) requis lors de l'insertion de la valeur. Devenir. C'est assez rapide.

Recommended Posts

ABC170 E - Comment résoudre sans utiliser le multiset de Smart Infants
Comment connaître le nombre de processeurs sans utiliser la commande sar
Examen de atcoder ABC158, jusqu'à la question E (Python)
[Circuit x Python] Comment résoudre symboliquement les équations de circuit en utilisant sympy
Journal d'enquête sur la façon d'optimiser les hyperparamètres LightGBM à l'aide d'Optuna
Résoudre ABC176 E en Python
Comment écrire un exemple d'implémentation Python du problème E15 en temps réel hors ligne
Comment écrire en temps réel hors ligne Résolution des problèmes E04 avec Python
Comment enregistrer une partie d'une longue vidéo en utilisant OpenCV
Comment POSTER sur un canal spécifié sans utiliser les WebHooks entrants de Slack
Comment installer Python à l'aide d'Anaconda
Résumé de l'utilisation de pandas.DataFrame.loc
Comment résoudre des équations linéaires simultanées
Résumé de l'utilisation de pyenv-virtualenv
Résumé de l'utilisation de csvkit
Résoudre des puzzles et 15 puzzles
Comment tester chaque version d'IE en utilisant Selenium avec modan.IE (VM)
Comment écrire hors ligne en temps réel J'ai essayé de résoudre E11 avec python
Appliquez la fonction à la ligne ou à la colonne de numpy.array sans utiliser la notation d'inclusion de liste
Comment écrire en temps réel hors ligne J'ai essayé de résoudre E12 avec python