[Chez Coder] Résoudre le problème de la dichotomie

Je veux être un professionnel compétitif, alors [Ce site (version AtCoder! Arimoto (Débutant))](https://qiita.com/drken/items/e77685614f3c6bf86f44#%E4%BE%8B%E9%A1%8C-2 -5-5warshall-floyd-% E3% 82% 92% E4% BD% BF% E3% 81% 86% E5% 95% 8F% E9% A1% 8C) pour résoudre le problème d'AtCoder et La fondation est solidifiée. Cette fois, j'ai résolu ce problème (C-fléchettes dans )est. C'est une dichotomie (montant de calcul O (logN)) qui est à la base des professionnels concurrents, mais il est assez difficile de décider où l'utiliser. ..

Résumé du problème

Lancez quatre flèches pour trouver le maximum du total des points touchés dans $ P_1, P_2, ..., P_N $ qui ne dépasse pas $ M $. Vous pouvez également choisir de ne pas lancer la flèche. S \leq M 1 \leq N \leq 1000 1 \leq M \leq 2 \times 10^8

Solution

La première chose qui me vient à l'esprit est de regarder tous les modèles de la manière $ (N + 1) ^ 4 $ ("+1" est l'ajout de la flèche P = 0 pour "ne pas lancer". ). En d'autres termes, c'est une recherche complète. Il peut être implémenté simplement en écrivant une quadruple boucle. Cependant, dans ce cas, le montant du calcul devient $ O (N ^ 4) $, et AC ne peut être effectué que si $ N = 100 à 200 $.

Donc, si vous le concevez et utilisez ** Dichotomy **, vous pouvez le résoudre en $ O (N ^ 2logN) $ time. C'est la méthode de la solution 3 décrite dans l'explication. Au lieu de "lancer la flèche quatre fois", pensez à "lancer deux fois et faire deux fois". Si vous lancez la flèche deux fois, vous obtiendrez moins de $ (N + 1) ^ 2 $. Commençons par trier ce résultat par $ Q_1, Q_2, ...., Q_r $. Le montant du calcul est de $ O (N ^ 2logN) $. → En d'autres termes, il peut être reformulé comme "lorsque le score est r, le total en lançant la flèche deux fois est M ou moins". En supposant que la somme des deux premières flèches est $ Q_i $, la solution optimale pour la somme des deux flèches restantes $ (Q_j) $ est Q_i + Q_j \leq M Parmi les $ j $ qui satisfont, celui avec le plus grand $ Q_j $ peut être trouvé. Un tel $ j $ peut être trouvé dans $ O (N ^ 2logN) $ time par une dichotomie. Le temps de préparation inclus, il peut être calculé en $ O (N ^ 2logN) $ temps dans son ensemble.

Voici un exemple de réponse utilisant python. La bissectrice de la bibliothèque facilite la réalisation d'une dichotomie.

import bisect

N, M = map(int, input().split())
p_list = [int(input()) for _ in range(N)]
p_list.append(0)
p_list.sort()
q_list = []

#Créer une liste de Qi
for i in range(N+1):
    for j in range(i, N+1):  #J'essaye d'éviter la duplication ... ★
        q = p_list[i] + p_list[j]
        if q <= M:
            q_list.append(q)
q_list.sort()

ans = 0
for q1 in q_list:
    #Recherche de bisection(Il doit être juste car il est calculé correctement lorsque le total est M)
    insert_index = bisect.bisect_right(q_list, M-q1)
    tmp_ans = q1 + q_list[insert_index-1]
    ans = max(ans, tmp_ans)

print(ans)

Au fait, la partie ★ du code,

for i in range(N+1):
    for j in range(N+1): 
        q = p_list[i] + p_list[j]
        if q <= M:
            q_list.append(q)

Quand je l'ai calculé et essayé de le trier plus tard, c'était MLE. La mémoire est importante.

Recommended Posts

[Chez Coder] Résoudre le problème de la dichotomie
[At Coder] Résoudre les problèmes typiques de la recherche de priorité en profondeur (DFS)
Résoudre le retard d'observation de l'interféromètre
Illustration des résultats du problème du sac à dos
Résoudre le problème de la libcudart manquante dans Ubuntu 16.04 + CUDA 8.0 + environnement Tensorflow
Essayez de résoudre le problème N Queen avec SA de PyQUBO
Résolution du problème de la valeur initiale des équations différentielles ordinaires avec JModelica
Résolvez les problèmes de somme partielle avec une recherche complète en Python
Utilisez Rasppie pour résoudre le problème de connexion Wi-Fi mobile insuffisante
Comment résoudre le problème d'emballage du bac
Criez Bonjour Reiwa! Au début de Reiwa!
Chez Coder (08/09/2020)
Résolvez le problème du voyageur de commerce avec OR-Tools
Résolvez le problème maximum de sous-tableau en Python
À la recherche du FizzBuzz le plus rapide en Python
Cours de base Python (à la fin de 15)
Essayez de résoudre le problème du fizzbuzz avec Keras
[AtCoder] Résoudre un problème de ABC101 ~ 169 avec Python
[Python] ABC133B (problème du triangle supérieur droit) [At Coder]
Confirmation des questions de base du professionnel de la concurrence ~ Recherche dichotomisée ~
Essayez de résoudre le problème de l'héritage de classe Python
Résoudre les problèmes de sac à dos à l'aide de pyomo et glpk
J'ai résolu le problème le plus profond d'Hiroshi Yuki.
Résolvez A ~ D du codeur yuki 247 avec python
Envoyer Gmail à la fin du processus [Python]
Rechercher par la valeur de l'instance dans la liste
Au moment de la mise à jour de python avec ubuntu
Supprimer une chaîne spécifique à la fin de python
ABC146C (dichotomie)
J'ai étudié le temps de calcul de "X dans la liste" (recherche linéaire / recherche dichotomique) et "X dans l'ensemble"
Remplir au codeur
Au Coder # 1 à minuit
Le 15e temps réel hors ligne, j'ai essayé de résoudre le problème de l'écriture avec python
[Python] AGC043A (problème de lecture et de DP) [At Coder]
[GoLang] Définissez un espace au début du commentaire
À la recherche du meilleur stéréogramme à points aléatoires (RDS).
Essayez de résoudre les problèmes / problèmes du "programmeur matriciel" (Chapitre 1)
Essayez de résoudre le problème d'affectation du médecin de formation avec Python
Obtenez l'image de "Suzu Hirose" par recherche d'images Google.
Regardez le score de Go d'un joueur de Go professionnel
[At Coder] Résolution d'un problème BFS typique [A - Darker and Darker]
J'ai essayé de résoudre le problème avec Python Vol.1
Tâches au démarrage d'un nouveau projet python
Le problème Zip 4 Gbyte est une histoire du passé
Un arbre de recherche de 2 minutes est un parent de la chaîne de hachage!?
Animer les bases de la planification dynamique et des problèmes de sac à dos
J'ai essayé de résoudre le problème de F02 comment écrire en temps réel hors ligne avec Python