[PYTHON] AtCoder Beginner Contest 054 Review of past questions

Time required

Problem A

When it is 1, it is different from the size of a normal integer, so consider it separately. (Is it a little more complicated than the normal A problem?)

answerA.py

a,b=map(int,input().split())
if a==1 or b==1:
    print("Alice" if a==1 else "Bob" if b==1 else "Draw")
else:
    print("Alice" if a>b else "Bob" if a<b else "Draw")

B problem

Decide which pixel of A the upper left of B corresponds to, and call the all_true function (determine if all pixels match) for each. (Is this also a little difficult in the B problem?)

answerB.py

n,m=map(int,input().split())
a=[list(input()) for i in range(n)]
b=[list(input()) for i in range(m)]
def all_true(i,j):
    global a,b
    for k in range(i,i+m):
        for l in range(j,j+m):
            if a[k][l]!=b[k-i][l-j]:
                return False
    return True
f=0
for i in range(n-m+1):
    for j in range(n-m+1):
        if all_true(i,j):
            f=1
            break
    if f==1:
        print("Yes")
        break
else:
    print("No")

C problem

I felt that it would be difficult because it is a problem of a pattern I have never seen, but when I look at the constraints, N is 8 at the maximum, so I first confirm that ** there is a lot of time to execute **. Here, when writing in the order in which the vertices are visited, all the vertices are visited only once, so you can see that ** the number of vertices included in the path is exactly N and all are different **. Also, the arrangement of N different numbers is N !, and 8! Is about $ 4 \ times10 ^ 4 $, so you can see that ** it seems that you can search all **. I think there are several ways to check if each path exists during a full search, but here we use an adjacency matrix because we check it repeatedly **. In other words, you can prepare an adjacency matrix first, check the arrangement of each vertex from the front, and check if there is a path between each of the two vertices.

answerC.py

import itertools
n,m=map(int,input().split())
p=[[0]*n for i in range(n)]#Adjacency matrix
for i in range(m):
    a,b=map(int,input().split())
    p[a-1][b-1]=1
    p[b-1][a-1]=1
seq=(i for i in range(n))
x=list(itertools.permutations(seq))
#print(x[0])
l=len(x)
ans=0
for i in range(l):
    k=x[i]
    if k[0]==0:
        for j in range(n-1):
            if p[k[j]][k[j+1]]!=1:
                break
        else:
            ans+=1
            #print(k)
    else:
        break
print(ans)

D problem

When I first saw it, I thought it was impossible to understand, but using DP made it easier than I expected. The reason for judging that it is DP is ** because the order does not matter, so it cannot be taken greedily, and the method of selecting the drug is O ($ 2 ^ n ) **. (In addition, O ( N \ times sum (a) \ times sum (b) $), so I confirmed that it fits in the time limit.) However, this time, when choosing a drug, it contains two substances, A and B, so it is necessary to ** DP in two dimensions **. In other words, consider a DP that creates a matrix that notes the amount of A and the amount of B when selecting N chemicals, and updates the matrix. After this, I'm just going to do a 2D version of Knapsack's DP, so I think it's faster to look at the code.

answerD.py

n,ma,mb=map(int,input().split())
el=[list(map(int,input().split())) for i in range(n)]
sa=sum(i[0] for i in el)
sb=sum(i[1] for i in el)

inf=1000000
#Initialize with inf
x=[[inf for j in range(sb+1)] for i in range(sa+1)]
#Don't forget to set the first element to 0
x[0][0]=0
for i in range(n):
    now=el[i]
    #It became extremely slow when using deepcopy, it is faster to make a normal array every time
    x_sub=[[0 for j in range(sb+1)] for i in range(sa+1)]
    #x_Update to sub(Because there are not more than one)
    for k in range(sa+1):
        for l in range(sb+1):
            if x[k][l]!=inf and k+now[0]<sa+1 and l+now[1]<sb+1:
                x_sub[k+now[0]][l+now[1]]=x[k][l]+now[2]
    #x_Move value from sub to x
    for k in range(sa+1):
        for l in range(sb+1):
                if x_sub[k][l]!=0:
                    x[k][l]=min(x[k][l],x_sub[k][l])
mi=min(sa//ma,sb//mb)
ans=inf
#Think from the smallest to the smallest possible one
for i in range(1,mi+1):
    ans=min(ans,x[ma*i][mb*i])
if ans==inf:
    print(-1)
else:
    print(ans)

Code that is constant times faster

answerD_better.py

n,ma,mb=map(int,input().split())
el=[list(map(int,input().split())) for i in range(n)]
sa=sum(i[0] for i in el)
sb=sum(i[1] for i in el)
sa1=sa+1
sb1=sb+1

inf=1000000
x=[[inf]*(sb1) for i in range(sa1)]
x[0][0]=0
for i in range(n):
    now=el[i]
    x_sub=[[0]*(sb1) for i in range(sa1)]
    for k in range(sa1):
        for l in range(sb1):
            if x[k][l]!=inf:
                if k+now[0]<sa1:
                    if l+now[1]<sb1:
                        x_sub[k+now[0]][l+now[1]]=x[k][l]+now[2]
    for k in range(sa1):
        for l in range(sb1):
                if x_sub[k][l]!=0:
                    x[k][l]=min(x[k][l],x_sub[k][l])
mi=min(sa//ma,sb//mb)
ans=inf
for i in range(1,mi+1):
    ans=min(ans,x[ma*i][mb*i])
if ans==inf:
    print(-1)
else:
    print(ans)