Critique du concours AtCoder Beginner Contest 153

Les résultats de cette fois

スクリーンショット 2020-01-27 11.04.13.png

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)

Recommended Posts

Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
Critique du concours AtCoder
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
Concours AtCoder Débutant 181 Remarque
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
Concours AtCoder Débutant 180 Remarque
AtCoder Grand Contest 048 Critique
Concours AtCoder pour débutants 156 WriteUp
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Concours AtCoder pour débutants 167
Concours AtCoder Débutant 183 Remarque
AtCoder Regular Contest 106 Évaluation
Concours AtCoder Débutant 184 Remarque
AtCoder Grand Contest 046 Critique
Revue du concours régulier AtCoder 104
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes