Résoudre avec Python [100 questions passées sélectionnées que les débutants et les intermédiaires devraient résoudre] (018 --023 recherche de bisection)

1. Objet

Résolvez 100 questions passées que les débutants et les intermédiaires devraient résoudre en Python. L'objectif est de devenir bleu clair lorsque vous avez terminé de tout résoudre.

Cet article s'intitule "Dichotomie 018 - 023".

2. Résumé

Puisque python a `` bisect '', vous pouvez l'utiliser pour la dichotomie, mais j'ai pensé que vous deviez vous entraîner à l'écrire vous-même afin de gérer les problèmes d'application.

3. Histoire principale

018 --023 Dichotomie

018. LDS_4_B --Dichotomie

Répondre

def find_num_by_binary(target_list, num):
    #num est la cible_Renvoie s'il est inclus dans la liste
    # target_la liste est supposée être dans l'ordre croissant
    bottom = 0
    top = len(target_list) - 1

    while top - bottom > 1:
        middle = (top + bottom) // 2
        if num == target_list[middle]:
            return True

        if num > target_list[middle]:
            bottom = middle
        else:
            top = middle
        
    if target_list[bottom] == num or target_list[top] == num:
        return True
    else:
        return False

if __name__ == "__main__":
    n = int(input())
    S = list(map(int, input().split()))
    q = int(input())
    T = list(map(int, input().split()))

    count = 0
    for t in T:
        count += find_num_by_binary(S, t)
    
    print(count)

Je l'ai écrit moi-même à cause du problème de base. La politique de dichotomie est

1. Commencez par organiser la liste des cibles par ordre croissant
2. Soit le plus petit nombre bas '' et le plus grand nombre haut```
3. Pour le moment, définissez le centre (pas le centre exact car il est divisé par 2 et tronqué) comme `` milieu '', et déterminez s'il correspond ou non à la valeur numérique cible.
4. S'il est jugé et ne correspond pas, vérifiez si la position du milieu '' se trouve du côté bas '' ou du côté `` haut ''.
5. S'il est sur le côté bas '', remplacez la valeur de haut '' par la valeur de milieu '', et inversement si c'est du côté haut ''. Remplacez la valeur de bas '' par la valeur de milieu ''
6. Répétez ceci pour toujours, et lorsque la différence entre bas '' et haut '' disparaît, elle se termine.
7. Enfin, cochez bas '' et haut '' au cas où, et renvoyez `` `retour``` est.

019. JOI 2009 Final 2 --Pizza

Répondre

import bisect

d = int(input()) #La longueur d'un tour de l'anneau
n = int(input()) #Nombre de magasins
m = int(input()) #Nombre de commandes
Stores = [0] + [int(input()) for _ in range(n-1)] #L'emplacement du magasin. Le 0ème est le magasin principal.
Stores.sort()
Deliveries = [int(input()) for _ in range(m)] #Destination de la livraison

total_distance = 0
for delivery in Deliveries:
    left_index = bisect.bisect_left(Stores, delivery)

    if left_index >= len(Stores):
        distance = min(abs(d - delivery), abs(delivery - Stores[left_index-1]))
    else:
        distance = min(abs(Stores[left_index] - delivery), abs(delivery - Stores[left_index-1])) 

    total_distance += distance

print(total_distance)

Explorez chaque destination de livraison en deux pour un éventail de magasins La politique est

1. Trouvez dans bisect_left où dans le tableau `` `` Stores vous pouvez insérer pour chaque destination (`livraison`)
2. Trouvez `distance``` en fonction du` left_index` `` renvoyé
3. Gardez à l'esprit que `left_index est supérieur ou égal à len (Stores) ``. À ce moment, le magasin principal sera également un magasin candidat après avoir fait le tour
4. La réponse est la somme des distances '' pour tous les livraisons ''

est.

distanceIl est difficile de penser aux points de soustraction lors du calculabs()Est utilisé pour en faire une valeur absolue. Si vous jugez left_index '' `` avec précision, il semble qu'il ne soit pas nécessaire d'en faire une valeur absolue.

20. AtCoder Beginner Contest 077 C - Snuke Festival

Répondre

import bisect
import itertools

N = int(input()) #Numéro de chaque pièce
A = list(map(int, input().split())) #petit
B = list(map(int, input().split())) #Modérer
C = list(map(int, input().split())) #grand

#C n'a pas besoin d'être trié
A.sort()
B.sort()

#Tout d'abord, maintenez l'index retourné en recherchant A pour chaque élément de B dans la moitié.
b_counts = [0] * N
for i in range(N):
    b_count = bisect.bisect_left(A, B[i])
    b_counts[i] = b_count

cumsum_b_counts = list(itertools.accumulate(b_counts))
cumsum_b_counts = [0] + cumsum_b_counts

#Dichotomiser B pour chaque élément de C. B tenu au-dessus_Profitez des comptes
total = 0
for c in C:
    count = bisect.bisect_left(B, c)
    total += cumsum_b_counts[count]

print(total)

Puisque la longueur de la liste est `` 10 ** 5 '' dans la contrainte, il semble que la boucle for ne puisse être tournée qu'une seule fois, mais d'abord, ignorez la contrainte et établissez une politique. La politique est

1. Dichotomisez `B``` sur l'élément de C``` pour obtenir l'index de la liste`` B```
2. Les éléments de `` B``` jusqu'à cet index sont ensuite recherchés pour `ʻA``` dans la moitié pour obtenir l'index.
3. La somme de cet indice est la réponse

est. Si la politique ci-dessus est déposée dans le code, ce sera comme suit.

#C'est TLE
import bisect

N = int(input()) #Numéro de chaque pièce
A = list(map(int, input().split())) #petit
B = list(map(int, input().split())) #Modérer
C = list(map(int, input().split())) #grand

#C n'a pas besoin d'être trié
A.sort()
B.sort()

total = 0
for c in C:
    b_count = bisect.bisect_left(B, c) #Quantité de b
    for b in B[:b_count]:
        a_count = bisect.bisect_left(A, b) #Quantité d'un
        total += a_count

print(total)

Avec ce code, l'exemple passera, mais à mesure que N augmente, le temps sera `` TLE '' et il ne sera pas dans le temps. Donc, à partir de là, réfléchissons à la façon de réduire de un la boucle for. Penser "Y a-t-il quelque chose qui est compté deux fois?"

for b in B[:b_count]:
        a_count = bisect.bisect_left(A, b)

Vous pouvez voir ici que nous comptons la même chose encore et encore. Par conséquent, je considérerai une méthode qui calcule la valeur numérique comptée ici à l'avance, la retient et l'utilise.

En guise de solution, les seules armes dont je dispose pour le moment sont le DP et la somme cumulative, donc si l'on considère l'utilisation de l'un ou l'autre, cette fois, il semble que la somme cumulée fonctionnera.

#Tout d'abord, maintenez l'index retourné en recherchant A pour chaque élément de B dans la moitié.
b_counts = [0] * N
for i in range(N):
    b_count = bisect.bisect_left(A, B[i])
    b_counts[i] = b_count

cumsum_b_counts = list(itertools.accumulate(b_counts))
cumsum_b_counts = [0] + cumsum_b_counts

En conservant la valeur recherchée de moitié une fois comme somme cumulée, il n'était pas nécessaire de recalculer à chaque fois et la quantité de calcul pouvait être réduite.

021. AtCoder Beginner Contest 023 D --Sooting King

Répondre

def is_OK(middle_score, H, S, N):
    remain_times = []
    for i in range(N):
        remain_time = (middle_score - H[i]) / S[i]
        remain_times.append(remain_time)
    remain_times.sort()

    for time, remain_time in enumerate(remain_times):
        if remain_time < time:
            return False
    
    return True

if __name__ == "__main__":
    N = int(input())
    H = []
    S = []
    for _ in range(N):
        h, s = map(int, input().split())
        H.append(h)
        S.append(s)

    #Les pénalités possibles sont la valeur minimale de la valeur initiale H à la valeur maximale de H après N secondes.
    #Allez trouver la bonne hauteur dans cette gamme

    #Obtenez des limites inférieures et supérieures
    min_score = min(H)
    max_score = 0
    for i in range(N):
        max_score = max(max_score, H[i] * S[i] * N)

    #Recherche dichotomisée
    while max_score - min_score > 1:
        middle_score = (max_score + min_score) // 2

        if is_OK(middle_score, H, S, N):
            max_score = middle_score
        else:
            min_score = middle_score
    
    print(max_score)

Personnellement, je ne suis pas doué pour ce type de dichotomie.

Si vous voulez le résoudre sans tenir compte de la quantité de calcul, pour le moment, trouvez toutes les hauteurs de 0 seconde à N secondes pour tous les ballons, et laissez les lignes être des bulles et les colonnes être des secondes `` N × N '' Vous pouvez penser à créer une matrice et à la diviser pour que la valeur maximale soit la plus petite possible. Cependant, puisque la contrainte de N est 10 ** 5, il n'est pas possible de créer un tableau bidimensionnel.

Pensons donc à la résolution en une dimension au lieu d'un tableau à deux dimensions. Au lieu de penser à «casser la valeur maximale la plus petite possible», pensez à rechercher «une hauteur qui permette à tous les ballons de se casser dans le temps». Il est difficile de changer cette façon de penser.

Si vous pouvez le faire, résolvez-le selon la politique suivante dans une recherche de 2 minutes

1. Calculez le min_score et le `` `` max_score qui peuvent être pris parce que la hauteur est recherchée.
2. Allez dans `` middle_score``` pour trouver le bon endroit entre les deux ci-dessus
3. Le jugement est fait par la fonction ```is_OK (middle_score, H, S, N) `` `
4. Cette fonction détermine si toutes les bulles sont divisibles dans middle_score```
5. Plus précisément, lorsque vous faites un jugement, utilisez Vrai '' et Faux '' pour déterminer si tous les ballons peuvent être brisés dans le délai (`` stay_time ''). revenir
6. Répétez les étapes 1 à 6 pour trouver le bon `` middle_score``` et c'est la réponse

est.

Concernant la partie où la dernière réponse est `print```, je me demande toujours si" max_score "est la réponse ou" `min_score" est la réponse. Dans un tel cas, j'ai essayé imprimer '' pour les deux et j'ai adopté celui qui est l'exemple d'entrée. Cette fois, c'était max_score ''.

022. Concours régulier AtCoder 054 B - Loi de Moore

Répondre

def cal_time(x, P):
    #Calculez le temps nécessaire pour utiliser un PC qui prend actuellement P années pour calculer après x années
    return x + P * pow(2, -x/1.5)

if __name__ == "__main__":
    tolerance = 10**(-8)
    P = float(input())

    bottom = 0
    top = 10**18 + 1

    while top - bottom > tolerance:
        middle1 = (2 * bottom + top) / 3
        middle2 = (bottom + 2 * top) / 3

        if cal_time(middle1, P) < cal_time(middle2, P):
            top = middle2
        else:
            bottom = middle1
    
    print(cal_time(bottom, P))

Si vous le résolvez normalement en mathématiques, vous pouvez trouver le temps de vous différencier et de prendre la valeur minimale, il semble donc que ce n'est pas si difficile (si vous êtes un étudiant actif ...). Cependant, quand il s'agit de le résoudre par programme, j'ai pensé que ce serait assez difficile sans savoir comment le faire. D'un autre côté, ce que je fais n'est pas très différent d'une dichotomie, et je pensais qu'une fois que j'aurais résolu le problème, ce serait tout à fait le cas.

La solution est une recherche de trois minutes. La politique est

1. Créez la fonction souhaitée cal_time (x, P)
2. Trouvez x qui est la valeur minimale de cette fonction
3. Raccourcissez progressivement l'espace entre les deux points bas '' et haut '' et trouvez le bon x (où l'erreur se situe dans la plage autorisée).
4. Pour cela, calculez le middle1 '' du côté bottom '' et le middle2 '' du côté top '' et utilisez la fonction `cal_time (x). , P) pour comparer les tailles
5. À la suite de la comparaison ci-dessus, remplacez celui par la valeur la plus élevée calculée sur le côté bas '' et le côté haut '' par `` milieu ''.
6. Répétez ce qui précède et terminez la recherche lorsqu'une erreur acceptable est atteinte.
7. Enfin, calculez le temps avec bas '' ou haut '' (peu importe car il est réduit à l'erreur), et c'est la réponse

est.

023. JOI 2008 Final 3 - Fléchettes

Répondre

import bisect

N, M = map(int, input().split()) #N est le nombre de cassures cibles (le nombre d'éléments de P), M est la barre pour marquer des points
#Si le score total S est M ou moins, ce sera S, et s'il est supérieur à M, il sera de 0 point.->Donnez simplement la valeur totale à la dernière minute
P = [int(input()) for _ in range(N)] #Chaque score cible
P.append(0) #Inclure 0 point lorsque vous ne lancez pas
P.sort()
double_score_list = []

for p1 in P:
    for p2 in P:
        score = p1 + p2
        if score > M: #Empêcher les ajouts inutiles
            break 
        double_score_list.append(score)
double_score_list.sort()

#Explorez-vous en deux
answer = 0
for double_score in double_score_list:
    target = M - double_score
    max_i = bisect.bisect_left(double_score_list, target) - 1

    score = double_score + double_score_list[max_i]
    if score > M:
        continue
    answer = max(answer, double_score + double_score_list[max_i])

print(answer)

La première chose qui vient à l'esprit est de créer une liste de points pouvant être gagnés à partir d'un P '' donné, puis d'utiliser une recherche dichotomique pour trouver le bon score qui ne dépasse pas le M ''. Cependant, cela nécessite quatre boucles for pour créer la liste, ce qui est peu probable étant donné que N '' est 10 ** 3 ''. La boucle for doit être réduite à au plus deux.

En considérant de réduire la boucle for à deux, lancer quatre fois est susceptible d'être divisé par deux s'il est divisé en deux. Il semble que vous devriez faire une liste de points qui peuvent être obtenus en 2 fois, y compris les points si vous ne lancez pas, et rechercher le bon score pour chaque score dans une recherche de 2 minutes.

La politique spécifique est

1. Créez une liste de points double_score_list``` qui peuvent être obtenus en 2 fois, y compris les points (0 point) lorsque vous ne lancez pas
2. À ce stade, mettez break pour ne pas inclure les points en double ou les points qui dépassent `` `` M dans la liste.
3. Effectuez une dichotomie sur tous les éléments de `double_score_list``` pour trouver le score maximum en dessous de` `''

est.