Ich möchte ein wettbewerbsfähiger Profi sein, also [Diese Seite (AtCoder-Version! Arimoto (Anfänger))](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) zur Lösung des AtCoder-Problems und Das Fundament ist verfestigt. Diesmal habe ich [dieses Problem] gelöst (https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf#page=6) (C-Darts in ) ist. Es ist eine Dichotomie (Berechnungsbetrag O (logN)), die die Grundlage für konkurrierende Profis bildet, aber es ist ziemlich schwierig zu entscheiden, wo sie verwendet werden soll. ..
Wirf vier Pfeile, um das Maximum der in $ P_1, P_2, ..., P_N $ getroffenen Gesamtpunkte zu ermitteln, die $ M $ nicht überschreiten. Sie können auch festlegen, dass der Pfeil nicht geworfen wird.
Das erste, was mir in den Sinn kommt, ist, alle Muster auf $ (N + 1) ^ 4 $ Weise zu betrachten ("+1" ist die Hinzufügung des Pfeils P = 0 für "nicht werfen". ). Mit anderen Worten, es ist eine vollständige Suche. Es kann einfach durch Schreiben einer Vierfachschleife implementiert werden. In diesem Fall wird der Berechnungsbetrag jedoch zu $ O (N ^ 4) $, und AC kann nur durchgeführt werden, wenn $ N = 100 bis 200 $.
Wenn Sie es also entwickeln und ** Dichotomie ** verwenden, können Sie es in $ O (N ^ 2logN) $ Zeit lösen. Dies ist die in der Erläuterung beschriebene Methode der Lösung 3.
Anstatt "den Pfeil viermal zu werfen", denken Sie an "zweimal werfen und zweimal machen". Wenn Sie den Pfeil zweimal werfen, erhalten Sie weniger als $ (N + 1) ^ 2 $. Sortieren wir dieses Ergebnis zuerst nach $ Q_1, Q_2, ...., Q_r $. Der Berechnungsbetrag beträgt $ O (N ^ 2logN) $.
→ Mit anderen Worten, es kann umformuliert werden als "wenn die Punktzahl r ist, ist die Summe, wenn der Pfeil zweimal geworfen wird, M oder weniger".
Unter der Annahme, dass die Summe der ersten beiden Pfeile $ Q_i $ ist, ist die optimale Lösung für die Summe der verbleibenden zwei Pfeile $ (Q_j) $
Unten finden Sie ein Beispiel für eine Antwort mit Python. Die Bibliothekshalbierung erleichtert die 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 = []
#Erstellen Sie eine Liste von Qi
for i in range(N+1):
for j in range(i, N+1): #Ich versuche, Doppelarbeit zu vermeiden ... ★
q = p_list[i] + p_list[j]
if q <= M:
q_list.append(q)
q_list.sort()
ans = 0
for q1 in q_list:
#Halbierungssuche(Es muss richtig sein, weil es korrekt berechnet wird, wenn die Summe M) ist.
insert_index = bisect.bisect_right(q_list, M-q1)
tmp_ans = q1 + q_list[insert_index-1]
ans = max(ans, tmp_ans)
print(ans)
Übrigens, der ★ Teil im 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)
Als ich es als berechnete und später versuchte, es zu sortieren, war es MLE. Gedächtnis ist wichtig.
Recommended Posts