[PYTHON] Critique du concours AtCoder Beginner Contest 153

Les résultats de cette fois

Impressions de cette époque

Cette fois, j'ai pu résoudre jusqu'à E, mais ce n'était pas trop difficile, donc c'était comme hmm. De plus, le problème F était un problème de niveau bleu clair et j'ai remarqué comment le résoudre dans les 5 minutes restantes, mais je ne pouvais pas le résoudre, et je l'ai résolu 50 minutes après la fin du concours. Je suis désolé ...

Problème A

Tout ce que vous avez à faire est de calculer en maths le nombre de fois dont vous avez besoin pour garder votre force physique en dessous de h

A.py

import math
h,a=map(int,input().split())
print(int(math.ceil(h/a)))

Problème B

Jugez si vous pouvez tuer avec le coup spécial total

B.py

h,n=map(int,input().split())
a=[int(i) for i in input().split()]
print("Yes" if sum(a)>=h else "No")

Problème C

Battez les monstres avec une force physique élevée avec un coup spécial.

C.py

n,k=map(int,input().split())
h=[int(i) for i in input().split()]
h.sort(reverse=True)

if k>=n:
    print(0)
else:
    print(sum(h[k:]))

Problème D

Dans ce numéro, nous nous concentrons sur le fait que des monstres de même force naissent lorsqu'ils sont séparés. En d'autres termes, quand il y avait un monstre avec n force physique au début, n → n // 2, n // 2 → (n // 2) // 2, (n // 2) // 2, (n // 2) La force physique du monstre diminue à // 2, (n // 2) // 2, et lorsque la force physique devient 1, elle devient 0 lors de la prochaine attaque. En d'autres termes, si // est répété pour n jusqu'à ce que n devienne 0, et que le nombre de /// 2 jusqu'à ce point soit k, le nombre total d'attaques sur les monstres est de 2 $ ^ 0 + 2 ^ 1. Il devient + 2 ^ 2 +… + 2 ^ {k-1} $. Par conséquent, $ 2 ^ k-1 $ doit être calculé par le nombre total de fois.

answerD.py

h=int(input())
cnt=0
while True:
    h=h//2
    cnt+=1
    if h==0:
        break
print(2**cnt-1)

E problème

** Le problème d'un nombre illimité de sacs à dos ** (mais faites attention à la limite supérieure) (j'ai choisi le sac à dos DP car il n'y a pas de restrictions telles que la magie à choisir dans l'ordre). Le tableau dp stocke la puissance magique minimale requise pour réduire la force physique du monstre i dans le i-ème élément. Notez que ce tableau n'a pas de limite sur le nombre d'éléments, et seuls les éléments qui ne sont pas inf doivent être mis à jour dans l'ordre. De plus, à la fin, la force physique du monstre devrait être réduite à 0 ou moins avec la puissance magique minimale, il suffit donc de trouver la puissance magique minimale qui peut réduire la force physique du monstre de h ou plus. Aussi, je ne l'ai pas passé en Python, mais réécrit le même code en C ++ et AC. Quand je l'ai essayé après le concours, j'ai pu le réussir avec PyPy.

answerE.py

h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
    a_sub,b_sub=map(int,input().split())
    a.append(a_sub)
    b.append(b_sub)
inf=10000000000000
ma=max(a)
dp=[inf]*(h+1+ma)
dp[0]=0
for i in range(n):
    x=[a[i],b[i]]
    for j in range(h+1+ma):
        if dp[j]!=inf:
            if j+x[0]<=h+ma:
                dp[j+x[0]]=min(dp[j+x[0]],dp[j]+x[1])
            else:
                break
print(min(dp[h:]))

answerE.cc

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;

signed main(){
  ll h,n;cin >> h >> n;
  vector<ll> a(n);
  vector<ll> b(n);
  for(ll i=0;i<n;i++){
    cin >> a[i] >> b[i];
  }
  ll inf=10000000000;
  ll ma=*max_element(a.begin(),a.end());
  vector<ll> dp(h+1+ma,inf);dp[0]=0;
  for(ll i=0;i<n;i++){
    for(ll j=0;j<h+1+ma;j++){
      if(dp[j]!=inf){
        if(j+a[i]<=h+ma){
          dp[j+a[i]]=min(dp[j+a[i]],dp[j]+b[i]);
        }else{
          break;
        }
      }
    }
  }
  cout << *min_element(dp.begin()+h,dp.end()) << endl;
}

Problème F

** Je veux utiliser des bombes pour vaincre les monstres aussi efficacement que possible **. Ici, arrangez les monstres dans un ordre coordonné. Premièrement, lorsque vous battez le monstre à l'extrême gauche, vous pouvez vaincre le monstre plus efficacement en ** alignant l'extrémité gauche de la section avec ce monstre **, et le nombre d'explosions requis à ce moment est ceil (h [0] / Il est clair que a) le sera. J'aimerais également enquêter sur les monstres impliqués dans cette explosion. Vous pouvez savoir à quel point cela s'effondre en ** vérifiant où se trouve l'extrémité droite de la section dans la dichotomie ** (car c'est à gauche de bisect_right, vous pouvez vérifier l'élément sur le côté le plus à droite de la section) Je vais. Jusqu'à présent, j'ai pu penser parfaitement pendant le concours. À ce rythme, vous pouvez voir qu'il est inefficace car il utilise une boucle for imbriquée pour réduire la force physique du monstre impliqué (le premier code ci-dessous). Ici, ** méthode Imosu peut être utilisée pour mettre à jour efficacement uniquement aux deux extrémités de la section **, donc Imosu Après avoir réfléchi à la loi, prenez la somme cumulée de la fin, et si la force physique du monstre est impliquée dans l'explosion et qu'elle est déjà égale ou inférieure à 0, sautez-la, et si elle est supérieure à 0, explosez autant de fois que nécessaire. Tout ce que vous avez à faire est de l'implémenter et cela ressemblera au deuxième code ci-dessous. (J'ai écrit la méthode Imosho plusieurs fois, donc c'était très difficile d'implémenter ** la simulation en même temps que la mise à jour **. En mots, j'ai fait beaucoup plus que ce à quoi je m'attendais. J'étais parfaitement conscient que je ne pouvais pas le faire, donc j'ai dû passer autant de temps pendant le concours ...)

answerF_TLE.py

import bisect
import math
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
cnt=0
for i in range(n):
    #print(cnt)
    if h[i]>0:
        m=math.ceil(h[i]/a)
        cnt+=m
        k=bisect.bisect_right(x,x[i]+2*d,lo=i)
        for j in range(i,k):
            h[j]-=(m*a)
print(cnt)

answerF.py

import bisect
import math
n,d,a=map(int,input().split())
xh=[list(map(int,input().split())) for i in range(n)]
xh.sort()
x=[xh[i][0] for i in range(n)]
h=[xh[i][1] for i in range(n)]
g=[0]*n
cnt=0
for i in range(n):
    if h[i]>0:
        m=math.ceil(h[i]/a)
        cnt+=m
        k=bisect.bisect_right(x,x[i]+2*d,lo=i)
        if i!=n-1:
            h[i]-=m*a
            g[i]-=m*a
            if k<n:
                g[k]+=m*a
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
    else:
        if i!=n-1:
            g[i+1]+=g[i]
            h[i+1]+=g[i+1]
print(cnt)