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

Benötigte Zeit

Impressionen

Ab diesem Zeitpunkt begann ich, die Bachacon-Funktion von AtCoder Problems zu verwenden! (Weil Estimated Perfomance herauskommt) Als ich es schon einmal gelöst habe, konnte ich überhaupt nicht mit dem D-Problem konkurrieren und habe es nicht überprüft, aber ich habe das ähnliche Problem reibungslos gelöst, weil ich es zuvor gelöst habe. Für das D-Problem ist es gut, sich der Ziffer DP bewusst zu sein, aber ich habe das Gefühl, viel gelernt zu haben.

Problem A

Sie können es mit 1 / t multiplizieren.

answerA.py

t,x=map(int,input().split())
print(t/x)

B-Problem

Vergleichen Sie die Summe der längsten Seite und der anderen Seiten.

answerB.py

n=int(input())
l=sorted(list(map(int,input().split())))
print("Yes" if l[-1]<sum(l[:-1]) else "No")

C-Problem

Wenn n> = m ist, können Sie Teile an allen Punkten platzieren, ohne sich zu bewegen, sodass sie 0 sind. Wenn n <m, wählen Sie die Zelle aus, in der jeder Frame platziert werden kann. Beim Experimentieren wird jedoch angenommen, dass zwischen $ X_i $ und $ X_ {i + 1} $ ($ X_i $ wird in aufsteigender Reihenfolge sortiert) Wenn.) $ Y_i $ ist, können Sie alle Quadrate besuchen, indem Sie mn verschiedene $ Y_i $ auswählen (umgekehrt, auch wenn Sie weniger $ Y_i $ auswählen, alle Ich kann die Messe nicht besuchen.) Daher können Sie das kleinste m-n von $ Y_i $ auswählen und die Summe ausgeben. Dieses Problem ist ein häufiges Muster und sollte gemeistert werden. (Es ist wichtig, dass ** es ein Abschnitt ist, den Sie durch Bewegen passieren ** und dass ** Sie den Abschnitt frei wählen können **.)

answerC.py

n,m=map(int,input().split())
x=sorted(list(map(int,input().split())))
y=sorted([x[i+1]-x[i] for i in range(m-1)])
if n>=m:
    print(0)
else:
    print(sum(y[:m-n]))

D Problem

Ich denke, dass es ein Problem mit einem hohen Lerneffekt ist, weil es notwendig ist, die Eigenschaften von XOR zu kennen und gleichzeitig die sehr häufige Idee der Ziffern-DP von Mustern von ** K oder weniger ** zu berücksichtigen. Die Grundidee von Digit DP usw. kann leicht unter Kenchons Artikel verstanden werden. Im Folgenden werde ich meine eigenen Standpunkte erläutern.

Achten Sie zunächst auf jede Ziffer, die die Basis von XOR bildet (es handelt sich um eine binäre Ziffer. Bitte beachten Sie, dass die folgende Ziffer eine binäre Ziffer ist). Zu diesem Zeitpunkt sollten Sie ** jede Ziffer maximieren **, aber die i-te Ziffer von $ X \ XOR \ A_k $ (k = 1 ~ N) ist 0 oder 1 und das i von $ A_k $ Wenn die Ziffer 0 ist, ist die i-te Ziffer von X 1 und wenn die i-te Ziffer von $ A_k $ 0 ist, kann die i-te Ziffer von X auf 1 gesetzt werden, um die Ziffer (1) zu maximieren. Ich werde. Zählen Sie daher, ob die i-te Ziffer von $ A_1 $ ~ $ A_N $ 0 oder 1 ist, und setzen Sie bei vielen ** 0s die i-te Ziffer von X auf 1 und bei vielen 1 die i-te Ziffer von X auf 0. ** ist der Fall, in dem die Summe von $ X \ XOR \ A_1 $ ~ $ X \ XOR \ A_N $ in der i-ten Ziffer maximiert wird. Es gibt hier jedoch auch eine Bedingung von 0 oder mehr und K oder weniger, daher werden wir diese Bedingung von hier aus betrachten. In Anbetracht des Falls, in dem es kleiner oder gleich K ist **, wenn von der oberen Ziffer aus gezählt wird, ist die i-te Ziffer gleich K und die i + 1-te Ziffer ist kleiner als K ** (dies). Das ist die Idee der Ziffer DP von Mustern unter K!). Beachten Sie auch, dass jede Ziffer hier 0 oder 1 ist.

Da sowohl 0 als auch 1 nach der i + 1-Ziffer genommen werden können, prüfen Sie zunächst, ob sowohl 0 als auch 1 mit der Prüfvariablen genommen werden können (initialisieren Sie zuerst mit False). Weiterhin sei X (X = 1 ~ K) die Zahl, die f maximiert. Wenn hier die j-te Ziffer 1 ist, wenn K von der oberen Ziffer aus betrachtet wird, kann X sowohl 0 als auch 1 annehmen. Wenn die j-te Ziffer von X 0 annimmt, ist die j-te Ziffer von X kleiner als K, so dass die nachfolgenden Ziffern 0 oder 1 frei nehmen können (setzen Sie check auf True). ). Wenn im Gegenteil die j-te Ziffer von K 0 ist, ist 1 größer als K, sodass nur 0 genommen werden kann, unabhängig von der j-ten Ziffer von $ A_1 $ ~ $ A_N $ (wobei check True ist). In diesem Fall können Sie entweder 0 oder 1) frei wählen. (↑ ** Diese Operation wird auch für Ziffern-DP mit Einschränkungen von K oder weniger verwendet, daher dachte ich, dass sie vertraut sein sollte **.)

Sie finden die Antwort, indem Sie die obige Idee implementieren und den Maximalwert (möglich unter K) in jeder Ziffer zu ans hinzufügen.

answerD.py

n,k=map(int,input().split())
a=list(map(int,input().split()))
ans=0
co=[0]*50
check=False
for i in range(49,-1,-1):
    for j in range(n):
        if (a[j]>>i)&1:
            co[i]+=1
    if (k>>i)&1:
        if co[i]>=n-co[i]:
            ans+=(co[i]*(2**i))
            check=True
        else:
            ans+=((n-co[i])*(2**i))
    else:
        if check:
            if co[i]>=n-co[i]:
                ans+=(co[i]*(2**i))
            else:
                ans+=((n-co[i])*(2**i))
        else:
            ans+=(co[i]*(2**i))
print(ans)