AtCoder Beginner Contest 054 Revue des questions précédentes

Temps requis

スクリーンショット 2020-01-14 11.29.53.png

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)

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 067 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 081 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 060 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes