Code de l'éducation forces Round 88 Bacha Review (8/4)
résultat
Impressions
Dans le problème D, je suis resté fidèle à une politique. Si je suis bloqué, je voudrais m'entraîner afin de pouvoir passer à une politique différente en examinant l'énoncé du problème. Je commence à voir du violet à Kodofo, alors je ferai de mon mieux. Je pense qu'AtCoder a beaucoup d'habitudes perdantes, alors j'espère pouvoir faire de mon mieux dans la mesure où je ne tomberai pas malade.
Problème A
Distribuez des cartes $ n $, y compris des $ m $ jokers, à $ k $ personnes Ici, la personne avec le plus de jokers gagne, et le score à ce moment-là est (le nombre de jokers que cette personne a) - (le plus grand nombre de jokers que les autres ont). Pour maximiser ce score, envisagez d'abord de ** maximiser le nombre de jokers du gagnant **, soit $ x = min (m, \ frac {n} {k}) $ Je vais. Et pensez à ** minimiser le plus grand nombre de jokers que d'autres ont ** Par conséquent, distribuez les jokers $ mx $ restants aux autres ** aussi uniformément que possible **, mais le plus grand nombre de jokers que d'autres ont est $ y = ceil (\ frac { mx} {k-1}) $. Par conséquent, la réponse est de demander $ x-y $.
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))
Problème B
Que ce soit pour transformer une tuile blanche de 1 $ \ fois 1 $ en noir au coût $ x $ ou deux tuiles blanches de 1 $ \ fois 2 $ dans la même rangée en noir au coût $ y $ Vous pouvez paver les carreaux de deux manières. En vertu de cela, le problème est de paver les carreaux au moindre coût.
Ici, lorsque $ y \ geqq 2 \ times x $, tous les carreaux blancs ne doivent être modifiés que par l'ancienne méthode. Par contre, lorsque $ 2 \ times x> y $, ** il est préférable de changer la couleur de la tuile par la dernière méthode , mais cela ne peut être fait que pour deux carrés consécutifs dans la même ligne. Par conséquent, dans ce cas, vous pouvez peindre deux carrés consécutifs dans chaque ligne dans l'ordre, et enfin peindre les carrés non peints par la première méthode. ( C'est une idée courante d'effectuer d'abord les opérations gênantes et de les ajuster plus tard! **)
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)
Problème C
J'essayais de résoudre le problème sans me débarrasser du bogue, mais ce dont je devrais être conscient en arrivant à la bonne réponse cette fois-ci, c'est de ** clarifier si la considération ou l'implémentation est fausse **.
Passons maintenant au problème. Tout d'abord, j'ai pensé à ce qui arrive au changement de température en ajoutant de l'eau une tasse à la fois dans l'ordre chaud → froid → chaud →… à partir du ** graphique de la ligne de pliage **. Ce sera comme suit.
Comme vous pouvez le voir sur le graphique, ** toujours $ \ frac {h + c} {2} $ pour les temps pairs et graduellement la température de l'eau pour les moments impairs $ \ frac {h + c} {2} $ Vous pouvez voir qu'il approche **. Par conséquent, $ 2 $ fois est le meilleur lorsque le $ t $ donné est inférieur ou égal à $ \ frac {h + c} {2} $.
Ici, considérons le cas où le $ t $ donné est plus grand que $ \ frac {h + c} {2} $, mais dans ce cas, un nombre impair de fois sera toujours la réponse (✳︎). De plus, en considérant le rapport entre la quantité d'eau chaude et l'eau froide à des moments impairs, la transition est $ 1: 0 \ rightarrow 2: 1 \ rightarrow 3: 2 \ rightarrow… $. Par conséquent, dans le cas d'un nombre impair de fois, de l'eau chaude est ajoutée $ x + 1 $ fois et de l'eau froide est ajoutée $ x $ fois. De plus, la température de l'eau à ce moment est $ \ frac {h \ times (x + 1) + c \ times x} {2 \ times x + 1} $, et considérons $ x $ qui est le plus proche de $ t $. Je vais.
En supposant qu'il existe $ x $ tel que $ \ frac {h \ times (x + 1) + c \ times x} {2 \ times x + 1} = t $, $ x = \ frac {ht } {2 \ times t -hc} $ tient. En réalité, $ x $ est un entier, donc quand la température de l'eau est la plus proche de $ t $, $ x $ est $ floor (\ frac {ht} {2 \ times t -hc}) $ ou $ ceil (\ frac {ht} {2 \ fois t -hc}) $ (✳︎). En dessous, la température de l'eau dans chaque cas est calculée par $ \ frac {h \ times (x + 1) + c \ times x} {2 \ times x + 1} $, ce qui est plus proche de $ t $. Faites une comparaison.
En fait, cette comparaison est une fraction, donc ** la précision n'est pas suffisante si elle est calculée telle quelle **. Ici, il est nécessaire d'améliorer la précision en utilisant le ** module Fraction ** qui exprime des nombres rationnels. Il existe également un module Decimal comme moyen d'améliorer la précision, mais cela ne convient pas car il s'agit d'un ** module pour exprimer avec précision les fractions décimales **. De plus, les ** modules décimaux peuvent provoquer des erreurs de division **.
Par conséquent, ce qui précède est mis en œuvre avec précision et devient comme suit.
✳︎… Ce qui précède (✳︎) nécessite une preuve, mais il est omis car il est facile de s'écarter de l'essence.
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)
Problème D
Je voulais en savoir plus sur la section, alors j'ai essayé de la résoudre en utilisant la méthode de l'échelle, mais cela n'a pas très bien fonctionné. ** La méthode de mise à l'échelle ne fonctionne que si la section remplit toujours les conditions **, et c'est une politique à éviter dans ce problème. J'aurais dû changer de politique ici.
J'ai pensé que je pourrais choisir une meilleure politique si j'étais conscient des points suivants.
① Il faut penser ** en excluant la valeur maximale ** ② La valeur maximale est de 61 façons au maximum (-30 ~ 30) ③ ** Les sous-séquences et les sections continues sont faciles à penser aux transitions, elles sont donc compatibles avec DP **
À partir des trois ci-dessus, on peut penser qu'il vaut mieux considérer un DP ** qui a une valeur maximale ** comme état. Autrement dit, $ dp [i] [j]: = $ (la valeur maximale d'une sous-colonne qui inclut le $ i $ th et a une valeur maximale de $ j $). Lorsqu'elle est placée de cette manière, la transition sera la suivante. De plus, dp contient -INF comme valeur initiale.
① En sélectionnant seulement $ a_i $
② Lorsqu'une sous-colonne a déjà été sélectionnée (sous $ dp [i-1] [j]! = -INF $)
(1) Quand $ j \ leqq a [i] + 30 $ ** La valeur maximale de la sous-colonne est $ a [i] + 30 $ **, donc $ dp [i] [a [i] +30] = max (dp [i] [a [i] +30] , dp [i-1] [j] + a [i] - (a [i] + 30-j)) $
(2) Lorsque $ j> a [i] + 30 $ ** La valeur maximale de la sous-colonne ne change pas **, donc $ dp [i] [j] = dp [i-1] [j] + a [i] $
La réponse peut être trouvée en implémentant ce qui précède et en trouvant la valeur maximale incluse dans dp. Notez également que ** la valeur maximale ne tombe pas en dessous de 0 **.
D.py
#l'a fait! !!
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):
#+N'oubliez pas 30
#Hajime
if i==0:
dp[i][a[i]+30]=0
continue
#Si vous le choisissez en premier
dp[i][a[i]+30]=0
#Si c'est continu
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))
Après le problème E
Je ne résoudrai pas cette fois.
Recommended Posts