[PYTHON] Bildungs-Codeforces-Runde 88 Bacha Review (8/4)
Ergebnis
Impressionen
Beim D-Problem habe ich mich an eine Richtlinie gehalten. Wenn ich nicht weiterkomme, möchte ich trainieren, damit ich durch Überprüfen der Problemstellung zu einer anderen Richtlinie wechseln kann. Ich fange an, lila in Kodofo zu sehen, also werde ich mein Bestes geben. Ich denke, AtCoder hat viele Gewohnheiten zu verlieren, deshalb hoffe ich, dass ich mein Bestes geben kann, soweit ich nicht krank werde.
Problem A
Verteilen Sie $ n $ Karten, einschließlich $ m $ Joker, an $ k $ Personen. Hier gewinnt die Person mit den meisten Jokern, und die Punktzahl zu diesem Zeitpunkt ist (die Anzahl der Joker, die diese Person hat) - (die größte Anzahl von Jokern, die andere Leute haben). Um diese Punktzahl zu maximieren, sollten Sie zunächst ** die Anzahl der Joker maximieren, die der Gewinner hat **, dh $ x = min (m, \ frac {n} {k}) $ Ich werde. Und erwägen Sie, die größte Anzahl von Jokern, die andere haben, zu minimieren. Verteilen Sie daher die verbleibenden $ mx $ -Joker so gleichmäßig wie möglich an andere **, aber die größte Anzahl an Jokern, die andere haben, ist $ y = lid (\ frac { mx} {k-1}) $. Daher lautet die Antwort, nach $ x-y $ zu fragen.
A.py
for _ in range(int(input())):
n,m,k=map(int,input().split())
x=min(m,n//k)
y=-((x-m)//(k-1))
print(max(0,x-y))
B-Problem
Ob eine weiße Kachel von $ 1 \ mal 1 $ zum Preis von $ x $ in Schwarz oder zwei weiße Kacheln von $ 1 \ mal 2 $ in derselben Reihe in Schwarz zum Preis von $ y $ umgewandelt werden sollen Sie können die Kacheln auf zwei Arten pflastern. Dabei besteht das Problem darin, die Fliesen zu den niedrigsten Kosten zu pflastern.
Wenn $ y \ geqq 2 \ times x $ ist, sollten hier alle weißen Kacheln nur mit der vorherigen Methode geändert werden. Wenn $ 2 \ times x> y $, ** ist, ist es am besten, die Kachelfarbe mit der letzteren Methode zu ändern , dies kann jedoch nur für zwei aufeinanderfolgende Quadrate in derselben Zeile durchgeführt werden. Daher können Sie in diesem Fall zwei aufeinanderfolgende Quadrate in jeder Zeile der Reihe nach malen und schließlich die unbemalten Quadrate nach der vorherigen Methode malen. ( Es ist üblich, zuerst mühsame Operationen durchzuführen und später anzupassen! **)
B.py
for _ in range(int(input())):
n,m,x,y=map(int,input().split())
a=[[j for j in input()] for i in range(n)]
ans=0
if y>=2*x:
for i in range(n):
ans+=a[i].count(".")*x
else:
for i in range(n):
for j in range(m-1):
if a[i][j]=="." and a[i][j+1]==".":
a[i][j]="*"
a[i][j+1]="*"
ans+=y
for i in range(n):
ans+=a[i].count(".")*x
print(ans)
C-Problem
Ich habe versucht, das Problem zu lösen, ohne den Fehler zu beseitigen, aber was ich hätte beachten müssen, als ich dieses Mal zur richtigen Antwort kam, war zu klären, ob die Überlegung oder die Implementierung falsch ist.
Kommen wir nun zum Problem. Zunächst dachte ich darüber nach, was mit der Temperaturänderung passiert, indem ich jeweils eine Tasse Wasser in der Reihenfolge heiß → kalt → heiß →… aus dem ** Faltliniendiagramm ** hinzufügte. Es wird wie folgt sein.
Wie Sie in der Grafik sehen können, ** immer $ \ frac {h + c} {2} $ für gerade Zeiten und allmählich die Wassertemperatur für ungerade Zeiten $ \ frac {h + c} {2} $ Sie können sehen, dass es sich nähert **. Daher ist $ 2 $ mal am besten, wenn das angegebene $ t $ kleiner oder gleich $ \ frac {h + c} {2} $ ist.
Betrachten Sie hier den Fall, in dem das angegebene $ t $ größer als $ \ frac {h + c} {2} $ ist. In diesem Fall ist jedoch immer eine ungerade Anzahl von Malen die Antwort (✳︎). In Anbetracht des Verhältnisses der Menge an heißem Wasser zu kaltem Wasser zu ungeraden Zeiten beträgt der Übergang $ 1: 0 \ rechtspfeil 2: 1 \ rechtspfeil 3: 2 \ rechtspfeil… $. Daher wird im Falle einer ungeraden Anzahl von Malen heißes Wasser $ x + 1 $ Mal und kaltes Wasser $ x $ Mal hinzugefügt. Außerdem beträgt die Wassertemperatur zu diesem Zeitpunkt $ \ frac {h \ times (x + 1) + c \ times x} {2 \ times x + 1} $ und berücksichtigt $ x $, das $ t $ am nächsten kommt. Ich werde.
Angenommen, es gibt $ x $, so dass $ \ frac {h \ times (x + 1) + c \ times x} {2 \ times x + 1} = t $, $ x = \ frac {ht } {2 \ times t -hc} $ gilt. In Wirklichkeit ist $ x $ eine ganze Zahl. Wenn also die Wassertemperatur $ t $ am nächsten kommt, ist $ x $ $ Boden (\ frac {ht} {2 \ mal t -hc}) $ oder $ Ceil (\ frac {ht}) {2 \ times t -hc}) $ (✳︎). Darunter wird die Wassertemperatur jeweils durch $ \ frac {h \ mal (x + 1) + c \ mal x} {2 \ mal x + 1} $ berechnet, was näher an $ t $ liegt. Einen Vergleich machen.
Tatsächlich ist dieser Vergleich ein Bruchteil, daher ** reicht die Genauigkeit nicht aus, wenn sie so berechnet wird, wie sie ist **. Hier ist es notwendig, die Genauigkeit durch Verwendung eines ** Bruchmoduls ** zu verbessern, das rationale Zahlen ausdrückt. Es gibt auch ein Dezimalmodul, um die Genauigkeit zu verbessern. Dies ist jedoch nicht geeignet, da es sich um ein ** Modul zum genauen Ausdrücken von Dezimalbrüchen ** handelt. Außerdem können ** Dezimalmodule Teilungsfehler verursachen **.
Daher wird das Obige genau implementiert und wird wie folgt.
✳︎… Das Obige (✳︎) erfordert einen Beweis, wird jedoch weggelassen, da es leicht ist, von der Essenz abzuweichen.
C.py
from fractions import Fraction
for _ in range(int(input())):
h,c,t=map(Fraction,input().split())
if 2*t<=(h+c):
print(2)
else:
x1=(h-t)//(2*t-h-c)
x2=x1+1
x1,x2=Fraction(x1),Fraction(x2)
y1,y2=Fraction(h*(x1+1)+c*x1)/Fraction(2*x1+1),Fraction(h*(x2+1)+c*x2)/Fraction(2*x2+1)
if abs(y1-t)<=abs(y2-t):
print(2*x1+1)
else:
print(2*x2+1)
D Problem
Ich wollte mich über den Abschnitt informieren, also habe ich versucht, ihn mit der Skalierungsmethode zu lösen, aber er hat nicht sehr gut funktioniert. ** Die Skalierungsmethode funktioniert nur, wenn der Abschnitt immer die Bedingungen erfüllt **. Dies ist eine Richtlinie, die in dieser Ausgabe vermieden werden sollte. Ich hätte hier die Richtlinien wechseln sollen.
Ich dachte, ich könnte eine bessere Politik wählen, wenn mir die folgenden Punkte bekannt wären.
① Sie müssen denken ** ohne den Maximalwert ** ② Der Maximalwert beträgt höchstens 61 Wege (-30 ~ 30). ③ ** Teilsequenzen und fortlaufende Abschnitte lassen sich leicht über Übergänge nachdenken und sind daher mit DP kompatibel **
Aus den obigen drei kann angenommen werden, dass es besser ist, einen DP ** mit einem ** Maximalwert als Zustand zu betrachten. Das heißt, $ dp [i] [j]: = $ (der Maximalwert einer Unterspalte, die das $ i $ th enthält und einen Maximalwert von $ j $ hat). Wenn auf diese Weise platziert, ist der Übergang wie folgt. Außerdem enthält dp -INF als Anfangswert.
① Wenn Sie nur $ a_i $ auswählen
② Wenn bereits eine Unterspalte ausgewählt wurde (unter $ dp [i-1] [j]! = -INF $)
(1) Wenn $ j \ leqq a [i] + 30 $ ** Der Maximalwert der Unterspalte ist $ a [i] + 30 $ **, also $ dp [i] [a [i] + 30] = max (dp [i] [a [i] + 30] , dp [i-1] [j] + a [i] - (a [i] + 30-j)) $
(2) Wenn $ j> a [i] + 30 $ ** Der Maximalwert der Unterspalte ändert sich nicht **, also $ dp [i] [j] = dp [i-1] [j] + a [i] $
Die Antwort kann gefunden werden, indem das Obige implementiert und der in dp enthaltene Maximalwert ermittelt wird. Beachten Sie auch, dass ** das Maximum nicht weniger als 0 ** beträgt.
D.py
#erledigt! !!
from itertools import groupby
n=int(input())
a=list(map(int,input().split()))
INF=100000000000000
dp=[[-INF]*61 for i in range(n)]
ans=-INF
for i in range(n):
#+Vergiss 30 nicht
#Hajime
if i==0:
dp[i][a[i]+30]=0
continue
#Wenn Sie es zuerst wählen
dp[i][a[i]+30]=0
#Wenn es kontinuierlich ist
for j in range(61):
if dp[i-1][j]==-INF:
continue
if j<=a[i]+30:
dp[i][a[i]+30]=max(dp[i][a[i]+30],dp[i-1][j]+a[i]-(a[i]+30-j))
else:
dp[i][j]=dp[i-1][j]+a[i]
ans=max(ans,max(dp[i]))
print(max(ans,0))
Nach dem E-Problem
Ich werde diesmal nicht lösen.
Recommended Posts