[Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil 5/22]

** Streben Sie einen hellblauen Codierer an! !! !! !! !! !! ** ** **

Damit [Richtlinien zur Verbesserung von AtCoder, einem von Red Coder gelehrten Wettbewerbsprofi [Zwischenausgabe: Ziel für hellblauen Coder! ]]( https://qiita.com/e869120/items/eb50fdaece12be418faa#2-3-%E5%88%86%E9%87%8E%E5%88%A5%E5%88%9D%E4%B8%AD%E7 % B4% 9A% E8% 80% 85% E3% 81% 8C% E8% A7% A3% E3% 81% 8F% E3% 81% B9% E3% 81% 8D% E9% 81% 8E% E5% 8E % BB% E5% 95% 8F% E7% B2% BE% E9% 81% B8-100-% E5% 95% 8F) (@ e869120)

AtCoder hat 100 gute pädagogische Fragen gesammelt, die für braune und grüne Codierer geeignet sind, um mit einer kleinen Anzahl von Fragen einen hellblauen Codierer oder eine Bewertung von 1200 zu erzielen.

"100 frühere Fragen, die Anfänger und Fortgeschrittene in diesem Artikel lösen sollten" Wird mit ** Python ** gelöst! Vielen Dank an @ e869120! !! !! !! !! !!

Link zum letzten Artikel

** Alle durchsuchen: Alle auflisten ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil 1/22] ** Vollständige Suche: Alle Aufzählungen zur Reduzierung der Anzahl der Straßen durch Ausarbeitung ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part2 / 22] ** Vollständige Suche: Bit vollständige Suche ** [[Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Teil3 / 22]] (https://qiita.com/rudorufu1981/items/74d5f37c26c62fc7a27f) ** Vollständige Suche: Vollständige Suche weiterleiten ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part4 / 22] ** Halbierungssuche ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part5 / 22] ** Suche nach Tiefenpriorität ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part6 / 22] ** Suche nach Breitenpriorität ** [Python] Ich habe versucht, 100 frühere Fragen zu lösen, die Anfänger und Fortgeschrittene lösen sollten [Part7 / 22]

** (Hinzugefügt am 2020/05/07) **

• Ergänzung Geben Sie aus dem Artikel (** Teil 6 **) in dieser Serie mit 100 Fragen ein input()→sys.stdin.readline().rstrip() Ich wechsle zu! [Python] Competitive Pro-Vorlage [At Coder] Ich habe auch einen Artikel für die Vorlage erstellt. Bitte verwenden Sie ihn, wenn Sie ~ mögen

"Teil 5" -Dichotomie-

Wir werden die folgenden 6 Fragen lösen!

Halbierungssuche

18 ALDS_4_B - Dichotomie Dies ist ein Grundproblem. Sie können es auch mit einer Karte lösen, aber versuchen Sie es mit einer Dichotomie. 19 JOI 2009 Finale 2 - Pizza 20 AtCoder Anfängerwettbewerb 077 C --Snuke Festival Es ist interessant. 21 AtCoder Anfängerwettbewerb 023 D - Shooting King Pädagogisch gut. 22 AtCoder Regular Contest 054 B - Moores Gesetz Es kann durch Differenzieren und Dichotomisieren gelöst werden. Da die Geschichte mit der dreiminütigen Suche verbunden ist, halte ich es auch für gut, dies zu überprüfen. 23 JOI 2008 Final 3 --Darts Dies ist ein Herausforderungsproblem, das Sie in zwei Hälften entwickeln und suchen können.

Voraussetzung Kenntnisse der Dichotomie

・ Ich werde einen Artikel schreiben, der auf den folgenden zwei Punkten basiert! ** ① Über Dichotomie ** Zunächst Kenchos Artikel Verallgemeinerung des Dichotomiealgorithmus - Empfehlung der Dichotomiemethode Lesen Sie mehr über die Dichotomie ** Verstehen Sie die Atmosphäre! ** ** **

** ② Danach, wie man die Python-Dichotomie implementiert ** Wie Die folgende Seite war leicht zu verstehen, also diese Seite AtCoder Must-See für graue, braune und grüne Leute! Wie schreibe ich eine Dichotomie, ohne sie fehlerhaft zu machen? ** Vorsichtig ** Lies über die Dichotomie ** Verstehe tief! ** ** **

18 ALDS_4_B - Dichotomie

Wenn Sie die Länge des Produktsatzes jedes Satzes (Satzes) nehmen, ist dies ein Schuss. Ich werde mein Bestes tun, um dies durch Dichotomisierung umzusetzen. Es war mein erstes Mal, dass ich eine Dichotomie implementierte. Als ich es gemäß der obigen Seite implementiert habe ** Es war unerwartet einfach zu implementieren! ** ** **

test.py

def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = I()
S = LI()
q = I()
T = LI()
ans = 0
def birarysearch(x):
    ok,ng = -1,n
    def is_ok(i):
        return S[i]<=x
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return S[max(ok,0)]==x
for x in T:
    if birarysearch(x):
        ans += 1
print(ans)

Das Maximum des ok Index ist die Antwort! Seien Sie jedoch vorsichtig, wenn der Index negativ wird, und setzen Sie ihn auf "max (ok, 0)"!

Eine andere Lösung
Wenn Sie die Bibliothek "bisect" verwenden können, verwenden wir sie! ** Wahnsinnig einfach zu implementieren! !! !! ** ** **

** Mit dem ok Index im obigen Code, Der Index von bisect.bisect (S, x) -1 im folgenden Code ist der gleiche! ** ** **

test.py

import bisect
def I(): return int(input())
def LI(): return list(map(int,input().split()))
n = I()
S = LI()
q = I()
T = LI()
ans = 0
for x in T:
    ok = bisect.bisect(S,x)-1
    if S[max(ok,0)]==x:
        ans += 1
print(ans)

• Bisect.bisect_right und bisect.bisect sind genau gleich! !!
• Es gibt auch "bisect.bisect_left", aber das Grundbild ist, dass nur "bisect.bisect" verwendet wird!

Sowieso

• ** ok (Version ohne Bibliothek) **
• ** bisect.bisect (A, x) -1 (Version mit Bibliothek) **

** Diese beiden Indizes sind Eisenplatten in der Dichotomie! !! !! ** ** **

19 JOI 2009 Finals 2-Pizza

Dies war auch ** unerwartet einfach zu implementieren! ** ** ** Sie können die Pizza aus dem Index "OK" oder dem Index rechts davon liefern, je nachdem, welcher Wert näher liegt.

test.py

def I(): return int(input())
d = I()
n = I()
m = I()
dn = [0]+sorted([I() for _ in range(n-1)])+[d]
mn = sorted([I() for _ in range(m)])
ans = 0
def binarysearch(x):
    ok,ng = -1,len(dn)
    def is_ok(i):
        return dn[i]<=x
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return min(x-dn[ok],dn[ok+1]-x)
for x in mn:
    ans += binarysearch(x)
print(ans)

• Apropos Zum Zeitpunkt der Eingabe enthielt "dn" auch die Informationen zur Zentrale "[0]" und "[d]"! !! !! Ich habe es unwissentlich gemacht, Wie man "[0]" oder "[d]" hinzufügt ← ** Es scheint, dass es einen Namen namens "Banheiho **" hat ~ Es kam heraus, als ich etwas googelte. Wie bei der ** Greedy-Methode ** gibt es möglicherweise andere Denkweisen für Programme, die Sie unwissentlich lernen, ohne Ihren Namen zu kennen!

Eine andere Lösung
Wenn Sie die Bibliothek bisect verwenden können, verwenden wir sie auch! ** Einfach zu implementieren! !! !! ** ** **

test.py

import bisect
def I(): return int(input())
d = I()
n = I()
m = I()
dn = [0]+sorted([I() for _ in range(n-1)])+[d]
mn = sorted([I() for _ in range(m)])
ans = 0
for x in mn:
    ok = bisect.bisect(dn,x)-1
    ans += min(x-dn[ok],dn[ok+1]-x)
print(ans)

20　AtCoder Beginner Contest 077 C - Snuke Festival Difficulty:1096 ** Ich konnte es auf den ersten Blick nicht lösen! !! !! ** ** **

bisect.bisect_left erscheint ... Es gab keine Ahnung ** basierend auf ** B, nicht A oder C ... Wie Sie der Erklärung entnehmen können, wurde das Problem ...! **Ich habe viel gelernt! !! !! ** ** **

test.py

import bisect
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
A = sorted(LI())
B = sorted(LI())
C = sorted(LI())
ans = 0
for b in B:
    ok_a = bisect.bisect_left(A,b)
    ok_c = bisect.bisect_right(C,b)
    ans += ok_a*(N-ok_c)
print(ans)

21 AtCoder-Anfängerwettbewerb 023 D - Shooting King

** Schwierigkeit: 1804! !! !! Blaues Problem! !! !! Ich konnte das auf den ersten Blick nicht lösen! !! !! ** ** **

Schauen Sie sich den Code derer an, die Kommentare abgeben können. Aber können Sie es lösen, wenn ein ähnliches Problem erneut auftritt? Wenn Sie das sagen, weiß ich immer noch nicht, welches Bild gelöst werden kann ... ** Unzureichende Übung für überwiegend schwierige Probleme! !! !! ** ** **

test.py

import numpy as np
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N = I()
HS = np.array([LI() for _ in range(N)])
H = HS[:,0]
S = HS[:,1]
rangeN = np.arange(N)
ok,ng = 10**9+10**9*10**9+1,0
def is_ok(i):
    T = (i-H)//S
    T.sort()
    return (T>=rangeN).all()
while abs(ok-ng)>1:
    mid = (ok+ng)//2
    if is_ok(mid):
        ok = mid
    else:
        ng = mid
print(ok)

• Eine der Schwächen der Bibliothek "bisect" ist, dass sie nur verwendet werden kann, wenn es sich um ein Array handelt. h = [i for i in range(10**9+10**9*10**9+1)] Wenn Sie so etwas schreiben, beträgt es 200 Millionen% TLE, sodass Sie die Bibliothek "halbieren" zu solchen Zeiten nicht verwenden können! Daher gibt es einige Muster, bei denen die Bibliothek "halbieren" nicht verwendet werden kann ** Sie müssen in der Lage sein, die Dichotomie selbst zu implementieren! ** ** **

22 AtCoder Regular Contest 054 B - Moores Gesetz

Difficulty:1268 ** Ich konnte das auf den ersten Blick nicht lösen! !! !! ** ** **

Es ist keine Dichotomie ** Es scheint, dass es durch die Dreiteilung gelöst werden kann **! Es ist keine monotone Zunahme oder monotone Abnahme, also scheint es, dass Sie keine Dichotomie machen können! Ich habe es implementiert, während ich verschieden gegoogelt habe, aber ich kann nur die Atmosphäre w erfassen

Ich bin auf dieses Problem gestoßen, als ich die erste Formel formulierte ... ** Dies sollte wahrscheinlich mit viel Übung bei schwierigen Problemen möglich sein! !! !! ** ** ** Wenn Sie konkret darüber nachdenken, 0 Jahre, 1 Jahr, 2 Jahre ..., können Sie eine Formel erstellen!

• x+P*2**(-x/1.5)

test.py

def F(): return float(input())
P = F()
high,low = P,0
def f(x):
    return x+P*2**(-x/1.5)
def is_high(i,j):
    return f(i)>=f(j)
while high-low>1*(10**-12):
    mid_right = (high*2+low)/3
    mid_left = (high+low*2)/3
    if is_high(mid_right,mid_left):
        high = mid_right
    else:
        low = mid_left
print(f(high))

Eine andere Lösung
Ich fühle mich ein wenig böse, aber kein w Die Antwort kann erhalten werden, indem der Wert von x durch 1. Differenzierung = 0 in "x + P * 2 ** (-x / 1,5)" eingesetzt wird. Der Wert von x des 1. Differentials = 0 ist [Diese Seite] (https://ja.wolframalpha.com/input/?i=%28x%2BP*%282**%28-x%2F1.5%29%29%29%27%3D+0) Lass uns benutzen!

als Ergebnis, x≈-2.16404 log(2.16404/P) Weil es herauskommt Danach setzen Sie einfach x in x + P * 2 ** (-x / 1.5)!

test.py

import math
def F(): return float(input())
P = F()
x = -2.16404*math.log(2.16404/P)
def f(x):
    return x+P*(2**(-x/1.5))
print(f(x) if x>0 else f(0))

** Ich habe AC gemacht! ** ** ** Apropos Als Voraussetzung ist "x> = 0" (ich kann nicht in die Vergangenheit zurückkehren!), Also werde ich die letzten Fälle trennen. Sie werden die Notwendigkeit einer Fallklassifizierung beim Debuggen von Eingabe / Ausgabe-Beispiel 2 bemerken!

23 JOI 2008 Final 3 --Darts

** Natürlich konnte ich es nicht auf den ersten Blick lösen! !! !! ** ** ** Oder besser gesagt, ich habe keine Ahnung, wo ich die Dichotomie verwenden soll. Natürlich ist es nicht möglich, ein "Vierfach für einen Satz" oder eine Vollbit-Suche durchzuführen. Denken Sie also in zwei oder zwei darüber nach! Wenn "N <= 1000", kann der Berechnungsbetrag "10 ^ 6" auf "doppelt für Aussage" erhöht werden, also frage ich mich, ob diese Zahl "1000" ein Hinweis war ...

Dieser Beitrag AtCoder-Version! Arimoto (Anfänger) Lösen von Pfeilen mit Python Ich konnte es mit Bezug auf ** sicher umsetzen! ** ** **

test.py

import bisect,itertools
def I(): return int(input())
def LI(): return list(map(int,input().split()))
N,M = LI()
P = [I() for _ in range(N)]
ans = 0
set_two_darts = set()
for x,y in itertools.product(P+[0],repeat=2):
    set_two_darts.add(x+y)
list_two_darts = sorted(set_two_darts)
ok_two_darts = bisect.bisect(list_two_darts,M)-1
if list_two_darts[ok_two_darts]<=M:
    ans = max(ans,list_two_darts[ok_two_darts])
for z in list_two_darts:
    remaining_point = M-z
    if remaining_point<=0:
        continue
    ok = bisect.bisect(list_two_darts,remaining_point)-1
    ans = max(ans,z+list_two_darts[ok])
print(ans)

Nächstes Mal werde ich die folgenden 4 Fragen lösen!

Tiefenprioritätssuche

24 ALDS_11_B - Tiefe Prioritätssuche Dies ist ein Grundproblem. 25 AOJ 1160-Wie viele Inseln gibt es? Die Anzahl der verbundenen Komponenten im Diagramm kann durch Suche nach Tiefenpriorität berechnet werden. 26 AtCoder-Anfängerwettbewerb 138 D - Ki Viele Baumstrukturprobleme verwenden die Suche nach Tiefenprioritäten. 27 JOI 2009 Qualifizieren der 4-dünnen Eisüberquerung Die Suche nach Tiefenprioritäten ist nicht nur eine Baumstruktur, sondern ein Problem, das uns sagt. Es kann mit einer rekursiven Funktion gelöst werden.

Part5/22 Ende!

Weiter (Teil 6/22)