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

Temps requis

スクリーンショット 2020-04-19 9.42.22.png

Impressions

"Le problème D est difficile, je ne sais pas!", Mais quand je l'ai revu, c'était un DP qui n'était rien. J'ai fait beaucoup d'erreurs récemment que je ne peux pas atteindre l'idée de DP en raison du problème de transition d'état, donc je ne le ferai jamais la prochaine fois.

Problème A

y est à moitié prix.

answerA.py


x,y=map(int,input().split())
print(x+y//2)

Problème B

Le nombre le plus proche de A est le nombre avec la plus petite différence absolue par rapport à A. De plus, puisque vous recherchez le numéro de point, vous devez également enregistrer le numéro de point.

answerB.py


n=int(input())
t,a=map(int,input().split())
h=[t-int(i)*0.006 for i in input().split()]
ans=[-1,1000000000]
for i in range(n):
    if abs(h[i]-a)<abs(ans[1]-a):
        ans=[i,h[i]]
print(ans[0]+1)

Problème C

La sortie est une combinaison du numéro de la préfecture à laquelle vous appartenez et du nombre de naissances dans cette ville. Par conséquent, tout d'abord, il est nécessaire de diviser la ville par préfecture. De plus, comme il est nécessaire de sortir dans l'ordre initialement reçu par l'entrée à la fin, divisez-le en tableaux pour chaque ville et mettez un ensemble de l'année de naissance et de l'ordre reçu par la première entrée dans chaque tableau. .. En vertu de cela, la disposition pour chaque préfecture est organisée dans l'ordre de l'année de naissance, combiné avec le numéro de préfecture, ** inséré dans le tableau de sortie avec l'ordre reçu dans la première entrée **, et dans la sortie finale, Vous pouvez sortir dans l'ordre ** reçu par la première entrée **.

answerC.py


n,m=map(int,input().split())
pyi=[[] for i in range(n)]
for i in range(m):
    p,y=map(int,input().split())
    pyi[p-1].append([y,i])
ans=[]
for i in range(n):
    pyi[i].sort()
    for j in range(len(pyi[i])):
        ans.append([(6-len(str(i+1)))*"0"+str(i+1)+(6-len(str(j+1)))*"0"+str(j+1),pyi[i][j][1]])
ans.sort(key=lambda x:x[1])
for i in range(m):
    print(ans[i][0])

Problème D

Tout d'abord, j'ai essayé de rechercher Mida avec bfs et dfs, mais je ne sais pas comment décider de la disposition des lignes horizontales qui ne passent pas ** et ** car le calcul ne peut pas être à temps car il peut être supérieur à ** 10 $ ^ 9 + 7 $. ** Alors j'ai abandonné. Tout d'abord, puisque Amidakuji se déplace de haut en bas, l'idée est que ** il est possible de formuler une formule progressive en se déplaçant de haut en bas ** (j'ai eu cette idée). ** DP ** est le plus compatible avec la formule progressive, et nous envisagerons une politique utilisant DP. Supposons maintenant que vous soyez sur la ligne verticale à la position X cm du haut et considérons sur quelle ligne horizontale vous pouvez vous déplacer à la position X + 1 cm. Ensuite, ** vous ne pouvez passer qu'à la ligne horizontale suivante ** et vous ne pouvez pas vous déplacer vers une ligne horizontale plus éloignée. Par conséquent, puisque nous savons bouger, soit l'élément de dp dp [X] [i], et soit le nombre ** lorsqu'il est à la position de la ième ligne verticale à partir de la gauche dans ** Xcm (indexé à 0). De plus, dp [x + 1] [i] est déterminé uniquement à partir de dp [x] [i-1], dp [x] [i], dp [x] [i + 1]. Ici, je voudrais considérer une combinaison de ** lignes horizontales non passantes (non pertinentes) ** quand je connais les lignes horizontales qui passent en Xcm, mais j'ai trouvé difficile de considérer séparément les lignes horizontales passantes et les lignes horizontales non passantes. C'était. Par conséquent, en notant que w est extrêmement petit (w $ \ leqq $ 8) et que ** en considérant toutes les combinaisons de lignes horizontales dans une recherche complète **, la condition (les deux barres horizontales partagent un point final) Considérons toutes les combinaisons de lignes horizontales qui satisfont (ne le font pas), et si les lignes horizontales sont connectées à i-1 → i, ajoutez dp [x] [i-1] à dp [x + 1] [i], et i + 1 → i Si la ligne horizontale est connectée à, ajoutez dp [x] [i + 1] à dp [x + 1] [i], et si ni la ligne horizontale de i-1 → i ni la ligne horizontale de i + 1 → i ne sont connectées Si vous ajoutez dp [x] [i] à dp [x + 1] [i], vous pouvez faire DP par O ($ HW2 ^ W $). Et puisque la barre verticale à atteindre est le K (K-1 s'il est indexé à 0), vous pouvez trouver dp [H] [K-1].

answerD.py


mod=10**9+7
h,w,K=map(int,input().split())
dp=[[0]*w for j in range(h+1)]
dp[0][0]=1
for i in range(1,h+1):
    for k in range(2**(w-1)):
        for l in range(w-2):
            if ((k>>l)&1) and ((k>>(l+1))&1):
                break
        else:
            for l in range(w):
                if l==0:
                    if ((k>>l)&1):
                        dp[i][l+1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
                elif l==w-1:
                    if ((k>>(l-1))&1):
                        dp[i][l-1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
                else:
                    if ((k>>l)&1) or ((k>>(l-1))&1):
                        if ((k>>l)&1):
                            dp[i][l+1]+=dp[i-1][l]
                        else:
                            dp[i][l-1]+=dp[i-1][l]
                    else:
                        dp[i][l]+=dp[i-1][l]
print(dp[h][K-1]%mod)

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 113 Revue des questions précédentes
AtCoder Beginner Contest 074 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