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

Benötigte Zeit

スクリーンショット 2020-04-02 18.52.21.png

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]))

Recommended Posts

AtCoder Beginner Contest 072 Rückblick auf frühere Fragen
AtCoder Beginner Contest 085 Rückblick auf frühere Fragen
AtCoder Beginner Contest 062 Rückblick auf frühere Fragen
AtCoder Beginner Contest 113 Rückblick auf frühere Fragen
AtCoder Beginner Contest 074 Rückblick auf frühere Fragen
AtCoder Beginner Contest 127 Rückblick auf frühere Fragen
AtCoder Beginner Contest 151 Rückblick auf frühere Fragen
AtCoder Beginner Contest 075 Rückblick auf frühere Fragen
AtCoder Beginner Contest 054 Rückblick auf frühere Fragen
AtCoder Beginner Contest 110 Rückblick auf frühere Fragen
AtCoder Beginner Contest 117 Rückblick auf frühere Fragen
AtCoder Beginner Contest 070 Rückblick auf frühere Fragen
AtCoder Beginner Contest 105 Rückblick auf frühere Fragen
AtCoder Beginner Contest 112 Rückblick auf frühere Fragen
AtCoder Beginner Contest 076 Rückblick auf frühere Fragen
AtCoder Beginner Contest 089 Rückblick auf frühere Fragen
AtCoder Beginner Contest 069 Rückblick auf frühere Fragen
AtCoder Beginner Contest 079 Rückblick auf frühere Fragen
AtCoder Beginner Contest 056 Rückblick auf frühere Fragen
AtCoder Beginner Contest 087 Rückblick auf frühere Fragen
AtCoder Beginner Contest 067 Rückblick auf frühere Fragen
AtCoder Beginner Contest 093 Rückblick auf frühere Fragen
AtCoder Beginner Contest 123 Überprüfung früherer Fragen
AtCoder Beginner Contest 078 Rückblick auf frühere Fragen
AtCoder Beginner Contest 081 Rückblick auf frühere Fragen
AtCoder Beginner Contest 047 Rückblick auf frühere Fragen
AtCoder Beginner Contest 060 Rückblick auf frühere Fragen
AtCoder Beginner Contest 104 Rückblick auf frühere Fragen
AtCoder Beginner Contest 121 Rückblick auf frühere Fragen
AtCoder Beginner Contest 126 Rückblick auf frühere Fragen
AtCoder Beginner Contest 090 Rückblick auf frühere Fragen
AtCoder Beginner Contest 103 Rückblick auf frühere Fragen
AtCoder Beginner Contest 061 Rückblick auf frühere Fragen
AtCoder Beginner Contest 059 Rückblick auf frühere Fragen
AtCoder Beginner Contest 044 Rückblick auf frühere Fragen
AtCoder Beginner Contest 083 Rückblick auf frühere Fragen
AtCoder Beginner Contest 048 Rückblick auf frühere Fragen
AtCoder Beginner Contest 124 Rückblick auf frühere Fragen
AtCoder Beginner Contest 116 Rückblick auf frühere Fragen
AtCoder Beginner Contest 097 Rückblick auf frühere Fragen
AtCoder Beginner Contest 088 Rückblick auf frühere Fragen
AtCoder Beginner Contest 092 Rückblick auf frühere Fragen
AtCoder Beginner Contest 099 Rückblick auf frühere Fragen
AtCoder Beginner Contest 065 Rückblick auf frühere Fragen
AtCoder Beginner Contest 053 Rückblick auf frühere Fragen
AtCoder Beginner Contest 094 Rückblick auf frühere Fragen
AtCoder Beginner Contest 063 Rückblick auf frühere Fragen
AtCoder Beginner Contest 107 Rückblick auf frühere Fragen
AtCoder Beginner Contest 071 Rückblick auf frühere Fragen
AtCoder Beginner Contest 064 Rückblick auf frühere Fragen
AtCoder Beginner Contest 082 Rückblick auf frühere Fragen
AtCoder Beginner Contest 084 Rückblick auf frühere Fragen
AtCoder Beginner Contest 068 Rückblick auf frühere Fragen
AtCoder Beginner Contest 043 Rückblick auf frühere Fragen
AtCoder Beginner Contest 098 Rückblick auf frühere Fragen
AtCoder Beginner Contest 114 Rückblick auf frühere Fragen
AtCoder Beginner Contest 045 Rückblick auf frühere Fragen
AtCoder Beginner Contest 120 Rückblick auf frühere Fragen
AtCoder Beginner Contest 108 Rückblick auf frühere Fragen
AtCoder Beginner Contest 106 Rückblick auf frühere Fragen