[PYTHON] AtCoder Beginner Contest 054 Revue des questions précédentes

Temps requis

Problème A

Quand il vaut 1, il est différent de la taille d'un entier normal, alors considérez-le séparément. (Est-ce un peu plus compliqué que le problème normal?)

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")

Problème B

Décidez à quel pixel de A correspond le coin supérieur gauche de B et appelez la fonction all_true (déterminez si tous les pixels correspondent) pour chacun. (Est-ce aussi un peu difficile dans le problème B?)

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")

Problème C

J'ai senti que ce serait difficile car c'est un problème de pattern que je n'ai jamais vu, mais quand je regarde les contraintes, N est 8 au maximum, donc je confirme d'abord que ** il y a beaucoup de temps à exécuter **. Ici, lors de l'écriture dans l'ordre dans lequel les sommets sont visités, tous les sommets ne sont visités qu'une seule fois, vous pouvez donc voir que le nombre de sommets inclus dans le chemin est exactement N et tous sont différents **. De plus, la disposition de N nombres différents est N! Et 8! Est d'environ 4 $ \ times10 ^ 4 $, donc vous pouvez voir que ** il semble que vous pouvez rechercher tout **. Je pense qu'il existe plusieurs façons de vérifier si chaque chemin existe lors d'une recherche complète, mais ici nous utilisons une matrice adjacente car nous la vérifions à plusieurs reprises **. En d'autres termes, préparez d'abord une matrice adjacente, vérifiez la disposition de chaque sommet depuis l'avant et vérifiez s'il existe un chemin entre chacun des deux sommets.

answerC.py

import itertools
n,m=map(int,input().split())
p=[[0]*n for i in range(n)]#Matrice adjacente
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)

Problème D

Quand je l'ai vu pour la première fois, je pensais que c'était impossible à comprendre, mais utiliser DP m'a rendu plus facile que prévu. La raison pour juger qu'il s'agit d'un DP est ** parce que l'ordre n'a pas d'importance, donc il ne peut pas être pris avec avidité, et la méthode de sélection du médicament est O (2 $ ^ n ) **. (De plus, O ( N \ times sum (a) \ times sum (b) $), j'ai donc confirmé que cela correspondait à la limite de temps.) Cependant, cette fois, lors du choix d'un médicament, il contient deux substances, A et B, il est donc nécessaire de ** DP en deux dimensions **. En d'autres termes, considérez un DP qui crée une matrice qui note la quantité de A et la quantité de B lors de la sélection de N produits chimiques, et met à jour la matrice. Après cela, je vais juste faire une version bidimensionnelle du DP de Knapsack, donc je pense qu'il est plus rapide de regarder le 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
#Initialiser avec inf
x=[[inf for j in range(sb+1)] for i in range(sa+1)]
#N'oubliez pas de mettre le premier élément à 0
x[0][0]=0
for i in range(n):
    now=el[i]
    #Il est devenu extrêmement lent lors de l'utilisation de deepcopy, il est plus rapide de créer un tableau normal à chaque fois
    x_sub=[[0 for j in range(sb+1)] for i in range(sa+1)]
    #x_Mettre à jour en sous(Parce qu'il n'y en a pas plus d'un)
    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_Déplacer la valeur de sous à 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
#Pensez du plus petit au plus petit possible
for i in range(1,mi+1):
    ans=min(ans,x[ma*i][mb*i])
if ans==inf:
    print(-1)
else:
    print(ans)

Code qui est constamment plus rapide

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)