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. ..
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.
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
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.