[PYTHON] AtCoder Beginner Contest 080 Review of past questions

Time required

Impressions

I feel that everything has been solved properly for the first time in a long time. However, since the D problem was deceived by the shape and decided the algorithm, I regret it.

Problem A

Just output the smaller one

answerA.py

n,a,b=map(int,input().split())
print(min(a*n,b))

B problem

To find the sum of each digit, divide by 10 in the while statement.

answerB.py

n=int(input())
k=n
f=0
while k!=0:
    f+=(k%10)
    k//=10
print("Yes" if n%f==0 else "No")

C problem

The problem of such a pattern makes you want to doubt DP etc., but even if you decide in advance whether to open in each time zone and do a full search, at most $ 2 ^ {10} -1 = 1023 $ (always once) Because it is open), I know I'll be in time. To see what happens to your profits when you decide whether to open or not in each time zone, check whether n stores in the shopping district are open in the time zone you decided to open (up to 10). Since it is recorded, it is O (n), and since it is O (n) because it calculates the profit corresponding to the number of checked stores, it can be seen that the calculation amount is in time.

answerC.py

n=int(input())
f=[list(map(int,input().split())) for i in range(n)]
p=[list(map(int,input().split())) for i in range(n)]
ma=-10000000000000
for i in range(1,2**10):
    check=[0]*n
    for j in range(10):
        if (i>>j) & 1:
            for k in range(n):
                check[k]+=f[k][j]
    ma_sub=0
    for i in range(n):
        ma_sub+=p[i][check[i]]
    ma=max(ma,ma_sub)
print(ma)

D problem

At first, I doubted the interval scheduling because I thought about the overlap of the sections, but it is not suitable for the interval scheduling to think about how many intervals ** overlap ** (it is suitable for choosing so that they do not overlap). I thought. As a result, this change in policy was successful. In the end, it was possible to think about ** how many sections are covered at the maximum **, so in other words, ** how many TV programs are being performed at each time **. After that, when updating the value of the interval **, it is efficient to use the imos method **, so I used imos. Furthermore, in this problem, ** the same channel can be recorded continuously even if the end and start times of a certain TV program are the same **, so make sure to use the imos method for each channel when counting the last I tried to calculate all together.

answerD.py

n,c=map(int,input().split())
imos=[[0 for i in range(c)] for j in range(10**5+1)]#1~10**5+1
for i in range(n):
    s,t,_c=map(int,input().split())
    imos[s-1][_c-1]+=1
    imos[t][_c-1]-=1
for i in range(1,10**5+1):
    for j in range(c):
        imos[i][j]+=imos[i-1][j]
imosans=[0]*(10**5+1)
for i in range(10**5+1):
    for j in range(c):
        imosans[i]+=(imos[i][j]>=1)
print(max(imosans))