Rückblick auf den AtCoder Beginner Contest 163 bis Frage E (Python)

Dies ist ein Übersichtsartikel für Anfänger von Wettkampfprofis.

Die Lösung, die ich hier schreibe, wird geschrieben, während ich den Kommentar und die Beiträge anderer Leute betrachte. Es ist möglicherweise nicht das, was Sie tatsächlich eingereicht haben.

A - Circle Pond Es ist ein Problem, den Umfang des Radius R auszugeben.

Umfang c bezüglich Radius r

c = 2\pi r

Es kann von gefunden werden.

import math
R = int(input())
print(2 * math.pi * R)

Da die Fehlertoleranz groß ist, scheint es nicht notwendig zu sein, das Umfangsverhältnis auf diese Weise abzulesen.

B - Homework

$ \ boldsymbol {A} $ Tage Wenn Sie die notwendigen Hausaufgaben für die Sommerferien machen, ist die Frage, wie viele Tage für die Sommerferien übrig bleiben.

(Anzahl der Tage während der Sommerferien) -Wenn (Gesamtarray) negativ ist-1, wird wie sonst ausgegeben. Wenn Sie max () verwenden, müssen Sie die if-Anweisung nicht verwenden.

N, M = map(int, input().split())
A = list(map(int, input().split()))

print(max(N - sum(A), -1))

C - management

Sie erhalten die Information "Mitarbeiter mit der Mitarbeiternummer $ i $, der die Mitarbeiternummer $ A_i $ als Chef hat". Es geht darum zu beantworten, wie viele Untergebene jeder Mitarbeiter hat.

Es dauerte die meiste Zeit, um die Problemstellung zu verstehen. Kurz gesagt, Sie werden nach der Verteilung der Zahlen gefragt.

Ich habe die Verteilung der Zahlen mit collection.Counter gezählt.

import collections
N = int(input())
A = list(map(int, input().split()))
count = collections.Counter(A)
for n in range(N):
  print(count[n+1])

D - Sum of Large Numbers

Es ist eine Frage, die Anzahl der möglichen Summen unter allen Kombinationen zu beantworten, die $ K $ oder mehr aus $ N + 1 $ Zahlen herausnehmen. Da jedoch jede Zahl die Form von $ 10 ^ {100} + i $ hat, werden die Summe von $ M $ und die Summe von $ M + 1 $ niemals übereinstimmen.

Ich habe keine Ahnung. Ist es nicht möglich, die Anzahl der Beträge zu formulieren? Ich habe versucht zu berechnen, welche Art von Verteilung die "Kombination von Summen, wenn $ M $ aus den Zahlen von 1 bis 9 genommen wird" wäre. Es zeigt die Verteilung der Summe, wenn die Ausgabe auf der $ m $ -Linie $ m $ nimmt.

Eigentlich habe ich hier aufgegeben. Wenn Sie sich das jetzt ansehen, erhalten Sie einen wichtigen Hinweis.

Bei Betrachtung dieser Ausgabe wird spekuliert, dass zwischen den Minimal- und Maximalwerten der Summe der Kombinationen keine Zahl fehlt. Wenn Sie dann den "Minimalwert der Summe" bzw. den "Maximalwert der Summe" berechnen, können Sie die Anzahl der kombinierten Summen ermitteln, wenn $ M $ genommen wird.

Der minimale Wert, wenn $ M $ genommen wird, ist "Summe der Zahlen bis zu $ M $", und der maximale Wert ist "Summe der Zahlen von $ N-M + 1 $". Der Rest ist die Anzahl der Kombinationen, die einen Unterschied von +1 haben können.

N, K = map(int, input().split())
mod = 10**9 + 7
count = 0
for n in range(K, N+2):
  maxSum = (n*(N + N-n+1))//2
  minSum = (n*(n-1))//2
  count += maxSum - minSum + 1
  count %= mod

print(count)

Ich ging daran vorbei. Ich wusste das, ohne auf den Kommentar zu schauen, also wollte ich ihn während des Wettbewerbs lösen. E - Active Infants

Angesichts des Koeffizienten $ A_i $ für jedes Kind, das an Position $ i $ existiert, besteht das Problem darin, den Maximalwert der Entfernung zu finden, um die sich das Kind um x den Koeffizienten bewegt.

Ich verstehe überhaupt nicht. Ich gab auf (TLE), indem ich in Not eine Round-Robin-Antwort abschickte.

`TLE Kerl.py`


import itertools 

N = int(input())
A = list(map(int, input().split()))
ureshisa = [
            [A[i] * abs(i-j) for j in range(N)] for i in range(N)
]
maxV = 0
for P in itertools.permutations(list(range(N))):
  maxV = max(maxV, sum([ureshisa[P[i]][i] for i in range(N)]))
print(maxV)

Ich habe es nicht verstanden, auch wenn ich mir die Erklärung angesehen habe, deshalb werde ich auf andere Antworten verweisen. Der folgende Code stammt aus dieser Antwort.

`Zitat.py`


# E - Active Infants

n = int(input())
a = list(map(int, input().split()))
assert len(a) == n

#Liste der Indizes
p = list(range(n))
p.sort(key=lambda i: a[i])

# dp[j] =Maximales Glück, wenn ich in den Abschnitt von Position j bis Breite i vom kleinsten platziert werde
dp = [0] * (n + 1)

for i in range(n):
    for j in range(n - i):
        dp[j] = max(dp[j]     + a[p[i]] * abs(p[i] - (j + i)),
                    dp[j + 1] + a[p[i]] * abs(p[i] - j))

print(dp[0])

Ich weiß es nicht, also werde ich den Prozess verfolgen

Folgen wir der Reihenfolge, was zu tun ist, wenn das Array "[1, 3, 4, 2]" angegeben wird.

Betrachten Sie zunächst die Platzierung eines Kindes (im Folgenden als $ a_0 $ bezeichnet) mit $ i = 0 $, das den Mindestwert von $ A_i $ hat.

Die Freude, $ a_0 $ an jeder der Positionen 0, 1, 2 und 3 zu platzieren, wird mit 0, 1, 2, 3 berechnet.

Speichern Sie diesen Wert als Array dp. Das Array "dp", wenn ein Kind $ a_0 $ von unten platziert wird, ist wie folgt

\mathrm{dp}_1= [0, 1, 2, 3]

Als nächstes platzieren Sie das Kind $ a_3 $ mit $ i = 3 $, wobei $ A_i $ der zweitkleinste Wert ist. Betrachten Sie jedoch nur den Status "Platzieren Sie einen hinter $ a_0 $" und "Platzieren Sie $ a_0 $ einen hinter".

Wenn $ a_0 $ bei $ i = 0 $ platziert wird, "belasse $ a_0 $ und platziere $ a_3 $ bei $ i = 1 $" "Setze $ a_0 $ auf $ i = 1 $" Schieben Sie es weg und platzieren Sie $ a_3 $ bei $ i = 0 $ ". Die Freude wurde mit 4 bzw. 7 berechnet. Lassen Sie nur den größeren Wert und setzen Sie "dp [0] = 7".

Wenn dies auf die gleiche Weise berechnet wird, wenn die Platzierung von $ a_0 $ $ i = 1 ist, sind 2 $, 6 bzw. 5 das Maximum. (Der Wert von "dp [3]" wurde hier absorbiert)

Also die beiden Säuglinge mit dem niedrigsten Koeffizienten ($ a_) Beim Anordnen von {03} $) nebeneinander

\mathrm{dp}_2 = [7, 6, 5]

Ist der Maximalwert, der jeder Position entspricht.

Betrachten Sie als nächstes die Platzierung des Säuglings $ a_1 $ mit dem dritten Koeffizienten von unten, $ i = 1 $.

Berechnen Sie "zwei Kleinkinder hintereinander hinter $ a_ {03} $ platzieren" und "zwei Kleinkinder hintereinander hinter $ a_ {03} $ platzieren".

Es wurde auf die gleiche Weise wie zuvor berechnet, und als die drei Säuglinge (genannt $ a_ {031} $) von unten nebeneinander platziert wurden, wurde es wie folgt erhalten.

\mathrm{dp}_3 = [10, 12]

Machen Sie dasselbe noch einmal für das Kind $ a_2 $ mit dem größten Koeffizienten $ A_i $.

Wenn $ a_ {031} $ bei $ i = 0 $ und $ a_2 $ bei $ i = 3 $, $ 14 $, $ a_ {031} $ bei $ i = 1 $ und $ platziert ist $ 20 $ wenn a_2 $ auf $ i = 0 $ gesetzt wird. Nimm den größeren.

\mathrm{dp}_4 = [20]

Jetzt hast du die Antwort.

Ich hol mein Verständnis nicht ein ... Müssen wir uns für diese Idee die Idee einfallen lassen, dass "das Kind mit dem M-ten Koeffizienten von unten immer an die" Reihe der Säuglinge vom 1. bis zum 1. M "angrenzt?" Ich fühle mich nicht intuitiv so, aber ich bin mir nicht sicher, ob ich es beweisen kann.

Nach der Idee des Kommentars wird die linke oder rechte Wand in der Reihenfolge vom Säugling mit dem höchsten Koeffizienten gefüllt. Kurz gesagt, es scheint, dass Sie dasselbe in umgekehrter Reihenfolge tun.

Das ist alles für diesen Artikel.

Referenz

https://atcoder.jp/contests/abc163/submissions/12150591 Frage E zitierte dies.