[PYTHON] AtCoder Beginner Contest 153 Review

This time's results

Impressions of this time

This time I was able to solve up to E, but it wasn't too difficult, so it felt like hmm. Also, the F problem was a light blue level problem and I noticed how to solve it in the remaining 5 minutes, but I could not solve it, and I solved it 50 minutes after the end of the contest. I'm sorry ...

Problem A

Just calculate the number of times you need to keep your fitness below h in math.ceil

A.py

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

B problem

Judge whether you can kill with the total special move

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

Defeat the monsters with high physical strength with a special move.

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 this issue, we focus on the fact that monsters of the same health are born when split. In other words, when there was a monster with n health at the beginning, n → n // 2, n // 2 → (n // 2) // 2, (n // 2) // 2, (n // 2) The monster's health decreases to // 2, (n // 2) // 2, and when the health becomes 1, it becomes 0 in the next attack. In other words, if // is repeated for n until n becomes 0, and the number of ///2 up to that point is k, the total number of attacks on monsters is $ 2 ^ 0 + 2 ^ 1. It becomes + 2 ^ 2 +… + 2 ^ {k-1} $. Therefore, $ 2 ^ k-1 $ should be calculated by the total number of times.

answerD.py

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

E problem

** Problem with unlimited number of knapsacks ** (but pay attention to the upper limit) (I chose knapsack DP because there are no restrictions such as which magic to choose in order). In the dp array, the i-th element stores the minimum magical power required to reduce the monster's health. Note that this array has no limit on the number of elements, and only the elements that are not inf should be updated in order. Also, in the end, the monster's physical strength should be reduced to 0 or less with the minimum magic power, so it is sufficient to find the minimum magic power that can reduce the monster's physical strength by h or more. Also, I rewrote the same code in C ++ and AC it, not in Python. When I tried it after the contest, I was able to pass it with 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;
}

F problem

** I want to use a bomb to defeat monsters as efficiently as possible **. Here, arrange the monsters in coordinate order. First, when defeating the monster on the far left, you can defeat the monster more efficiently by ** aligning the left end of the section with that monster **, and the number of explosions required at this time is ceil (h [0] / It is clear that a) will be. Also, I would like to investigate the monsters involved in this blast. You can find out how much this collapses by ** checking where the right end of the section is in a binary search ** (because it is one left of bisect_right, you can check the rightmost element in the section). I will. So far I have been able to think perfectly during the contest. At this rate, you can see that it is inefficient because it uses a nested for loop to reduce the physical strength of the monster involved (the first code below). Here, ** Imosu method can be used to efficiently update only at both ends of the section **, so Imosu After considering the law, take the cumulative sum from the end, and if the monster's physical strength is involved in the explosion and it is already 0 or less, skip it, and if it is greater than 0, explode as many times as necessary. All you have to do is implement it and it will look like the second code below. (I wrote the potato method a couple of times, so it was very difficult to implement ** simulation at the same time as updating **. In words, I did a lot more than I expected. I was keenly aware that I couldn't do it, so I had to pass this much during the contest ...)

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)