[PYTHON] AtCoder Beginner Contest 094 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Da ich schon einmal dort war, ist dies die zweite Frage der Vergangenheit. Ich kann vollständig antworten, wenn es auf diesem Niveau ist, aber ich möchte in der Lage sein, mit etwas auf einem etwas höheren Niveau fest zu konkurrieren.

Problem A

Beachten Sie, dass sowohl a <= x als auch a + b> = x sein muss.

answerA.py

a,b,c,d=[int(input()) for i in range(4)]
print(min(a,b)+min(c,d))

B-Problem

Überlegen Sie, wie viele Mautstellen es für 1 ~ x bzw. x ~ n gibt. Wenn Sie die Anzahl der Mautstellen von 1 bis x zählen, können Sie auch die Anzahl der Mautstellen von x bis n ermitteln.

answerB.py

n,m,x=map(int,input().split())
a=list(map(int,input().split()))
ans=0
for i in a:
    if i<x:
        ans+=1
    else:
        break
print(min(ans,m-ans))

C-Problem

In Bezug auf den Medianwert ist, da n eine gerade Zahl ist, die n // 2. Zahl oder die n // 2 + 1. Zahl der Medianwert, wenn die Zahlen 1 bis n in aufsteigender Reihenfolge nummeriert werden. Wenn die n // 2. Zahl in der 1. weggelassen wird, ist die n // 2 + 1. Zahl der Medianwert, und wenn die n // 2 + 1. bis n-te Zahl weggelassen wird, ist n /// Die zweite Zahl ist der Median. (** Ich habe ein Experiment durchgeführt und es bestätigt. **)

answerC.py

n=int(input())
x=list(map(int,input().split()))
y=sorted(x)
k,l=y[n//2-1],y[n//2]
for i in range(n):
    if x[i]<=k:
        print(l)
    else:
        print(k)

D Problem

Zunächst ist für $ \ _ {a_i} C \ _ {a_j} $ klar, dass beim Fixieren von ** $ a \ _j $ je größer $ a \ _i $, desto größer **. Daher wird ** $ a \ _i $ als die größte von a ** bestimmt, sodass nur eine Variable von ** $ a \ _j $ ** bestimmt werden muss. Wenn daher $ \ _ {max (a)} C \ _ {a_j} $ verwendet wird, um die Elemente eines anderen als max (a) als $ a_j $ zu berechnen und ihre Größen verglichen werden, ist der Maximalwert O (n). Hier gibt es eine Falle, obwohl sie gesucht zu sein scheint. Dies liegt daran, dass ** $ \ _ {max (a)} C \ _r $ nicht mit O (1) ** berechnet werden kann. Wenn Sie eine Tabelle für die Kombinationsberechnung erstellen, wird diese von O (1) berechnet, aber es wird O (n) benötigt, um die Tabelle vorzubereiten, sodass sie nicht rechtzeitig ist (n ist bis zu $ 10 ^ 9 $). Wenn Sie also $ \ _ {max (a)} C_r $ berechnen, werden Sie feststellen, dass Sie das Zeitlimit nicht einhalten können. Lassen Sie uns nun darüber nachdenken, $ a_j $ zu finden, wenn ** $ \ _ {max (a)} C \ _ {a_j} $ das Maximum ist, ohne ** zu berechnen. Dann können Sie sehen, dass $ a_j $ so nahe wie möglich an n / 2 maximiert wird (ich werde den Beweis weglassen, weil es ein Ärger ist, aber es ist schwierig zu beweisen, dass $ \ _nC \ _r = \ _nC \ _ {nr} $ verwendet wird Es sieht nicht so aus.) Daher ist die Antwort das Element eines ausschließenden Maximums (a), das dem Maximum (a) / 2 am nächsten kommt. Dies ermöglichte es uns, $ \ _nC \ _r $ zu finden, ohne es zu berechnen. Nach der Implementierung des obigen ist der Code wie folgt.

answerD.py

n=int(input())
a=sorted(list(map(int,input().split())))
b=a[n-1]
a.pop(n-1)
ans=0
for i in range(n-1):
    if abs(b/2-a[ans])>abs(b/2-a[i]):
        ans=i
print(str(b)+" "+str(a[ans]))