[PYTHON] AtCoder Beginner Contest 153 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Diesmal konnte ich bis zu E lösen, aber es war nicht allzu schwierig, also fühlte es sich an wie hmm. Außerdem war das F-Problem ein hellblaues Level-Problem und ich bemerkte, wie es in den verbleibenden 5 Minuten gelöst werden konnte, aber ich konnte es nicht lösen und löste es 50 Minuten nach dem Ende des Wettbewerbs. Es tut mir Leid ...

Problem A

Alles, was Sie tun müssen, ist in math.ceil zu berechnen, wie oft Sie Ihre körperliche Stärke unter h halten müssen

A.py

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

B-Problem

Beurteilen Sie, ob Sie mit dem gesamten Spezialzug töten können

B.py

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

C-Problem

Besiege die Monster mit hoher körperlicher Stärke mit einem Spezialzug.

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:]))

D Problem

In dieser Ausgabe stellen wir fest, dass beim Teilen Monster gleicher Stärke geboren werden. Mit anderen Worten, wenn es am Anfang ein Monster mit n physischer Stärke gab, n → n // 2, n // 2 → (n // 2) // 2, (n // 2) // 2, (n // 2) Die physische Stärke des Monsters verringert sich auf // 2, (n // 2) // 2, und wenn die physische Stärke 1 wird, wird sie beim nächsten Angriff 0. Mit anderen Worten, wenn // für n wiederholt wird, bis n 0 wird und die Anzahl von /// 2 bis zu diesem Punkt k ist, beträgt die Gesamtzahl der Angriffe auf Monster $ 2 ^ 0 + 2 ^ 1. Es wird + 2 ^ 2 +… + 2 ^ {k-1} $. Daher sollte $ 2 ^ k-1 $ durch die Gesamtzahl der Male berechnet werden.

answerD.py

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

E Problem

** Das Problem einer unbegrenzten Anzahl von Rucksäcken ** (aber achten Sie auf die Obergrenze) (Ich habe mich für Rucksack DP entschieden, da es keine Einschränkungen gibt, z. B. welche Magie in der Reihenfolge ausgewählt werden soll). Im dp-Array speichert das i-te Element die minimale magische Kraft, die erforderlich ist, um die physische Stärke des Monsters zu verringern. Beachten Sie, dass dieses Array keine Begrenzung für die Anzahl der Elemente hat und nur die Elemente, die nicht inf sind, der Reihe nach aktualisiert werden sollten. Am Ende sollte die physische Stärke des Monsters mit der minimalen magischen Kraft auf 0 oder weniger reduziert werden, sodass es ausreicht, die minimale magische Kraft zu finden, die die physische Stärke des Monsters um h oder mehr reduzieren kann. Außerdem habe ich es nicht in Python übergeben, sondern den gleichen Code in C ++ und AC neu geschrieben. Als ich es nach dem Wettbewerb versuchte, konnte ich es mit PyPy bestehen.

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;
}

F Problem

** Ich möchte Bomben einsetzen, um Monster so effizient wie möglich zu besiegen **. Ordne hier die Monster in koordinierter Reihenfolge an. Erstens, wenn du das Monster ganz links besiegst, kannst du das Monster effizienter besiegen, indem du ** das linke Ende des Abschnitts an diesem Monster ausrichtest ** und die Anzahl der zu diesem Zeitpunkt erforderlichen Explosionen ist Ceil (h [0] / Es ist klar, dass a) sein wird. Außerdem möchte ich die Monster untersuchen, die an dieser Explosion beteiligt sind. Sie können herausfinden, wie stark dies zusammenbricht, indem Sie ** überprüfen, wo sich das rechte Ende des Abschnitts in der Dichotomie befindet ** (da es sich um ein linkes Ende von bisect_right handelt, können Sie das Element ganz rechts im Abschnitt überprüfen). Ich werde. Bisher konnte ich während des Wettbewerbs perfekt denken. Bei dieser Geschwindigkeit können Sie sehen, dass es ineffizient ist, da es eine verschachtelte for-Schleife verwendet, um die physische Stärke des betroffenen Monsters zu verringern (der erste Code unten). Hier kann ** Imosu-Methode verwendet werden, um nur an beiden Enden des Abschnitts ** effizient zu aktualisieren, also Imosu Nachdem Sie über das Gesetz nachgedacht haben, nehmen Sie die kumulative Summe vom Ende. Wenn die physische Stärke des Monsters an der Explosion beteiligt ist und sie bereits 0 oder weniger beträgt, überspringen Sie sie und explodieren Sie so oft wie nötig, wenn sie größer als 0 ist. Alles was Sie tun müssen, ist es zu implementieren und es wird wie der zweite Code unten aussehen. (Ich habe die Imosho-Methode ein paar Mal geschrieben, daher war es sehr schwierig, ** Simulation gleichzeitig mit Aktualisierung ** zu implementieren. Mit anderen Worten, ich habe viel mehr getan, als ich erwartet hatte. Ich war mir sehr bewusst, dass ich es nicht schaffen konnte, also musste ich während des Wettbewerbs so viel bestehen ...)

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)