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

Temps requis

スクリーンショット 2020-04-01 16.39.23.png

Impressions

C'est une question passée que j'ai résolue auparavant, mais j'ai refait la même erreur avec le problème D. Je voudrais mentionner le contenu de l'erreur dans le problème D.

Problème A

Puisque nous avons un nombre infini de devises de 500 yens, demandez-vous si le reste de la division de n par 500 est inférieur à a.

answerA1.py


n=int(input())
a=int(input())
print("Yes" if n%500<=a else "No")

Problème B

Alice prend les index indexés à 0 et les index pairs dans l'ordre décroissant, et Bob prend ceux indexés impairs, ce qui est une stratégie pour maximiser leurs propres scores.

answerB.py


n=int(input())
a=sorted(list(map(int,input().split())),reverse=True)
ans=0
for i in range(n):
    if i%2==0:
        ans+=a[i]
    else:
        ans-=a[i]
print(ans)

Problème C

Pour la i-ème ligne, il s'agit de $ a_i + b_1, a_i + b_2, a_i + b_3 $, et pour chaque ligne (valeur dans la deuxième colonne-1 valeur dans la première colonne) et (valeur dans la troisième colonne-deuxième colonne). ) Les conditions nécessaires pour que les informations de Takahashi soient correctes, et il ressort clairement des expériences qu'il suffit de fixer la valeur de a de manière appropriée lorsque cette condition est satisfaite. (L'explication est appropriée, mais elle est claire lorsque vous calculez réellement (valeur dans la deuxième colonne-valeur dans la première colonne) et (valeur dans la troisième colonne-valeur dans la deuxième colonne) respectivement.)

answerC.py


c=[list(map(int,input().split())) for i in range(3)]
x=c[0][2]-c[0][1]
y=c[0][1]-c[0][0]
for i in range(1,3):
    if c[i][1]-c[i][0]!=y:
        print("No")
        break
    if c[i][2]-c[i][1]!=x:
        print("No")
        break
else:
    print("Yes")

Problème D

Je me suis souvenu comment résoudre ce problème car c'était impressionnant de le résoudre avant, mais j'ai fait beaucoup d'erreurs à la fin. Sunuke veut améliorer son score autant que possible, il doit donc changer autant de carrés que possible en noir. Cependant, si vous modifiez trop de cases, vous ne pourrez pas atteindre l'objectif. En d'autres termes, tout ce que vous avez à faire est de tout remplir sauf les cases que Kenusu suit pour atteindre l'objectif, et ** pour maximiser, vous pouvez tout remplir sauf le chemin le plus court. Par conséquent, ce problème peut être considéré comme un simple problème d'itinéraire le plus court. J'ai écrit le code avec dfs. Cependant, dans le cas de Python, la limite supérieure de la profondeur de récurrence est fixée par chaque environnement, donc `` sys.setrecursionlimit (x) '' définit la limite de récurrence à x **. .. Cependant, si ce ** x est trop grand, il sera TLE, donc il devrait être aussi petit que possible **. Dans ce problème, H est 50 et W est 50, donc j'ai pensé que ce serait bien si c'était 2500 ou plus, mais depuis qu'il est devenu RE, il semble y avoir un modèle où le nombre de récurrence est supérieur à 2500 (je ne peux pas y penser ...) .. J'ai essayé de définir le nombre de répétitions à la limite, mais cela n'a pas fonctionné à cause de l'intention de Writer. À la fin, je l'ai fait fonctionner en accélérant avec ** PyPy . De plus, la recherche de priorité de largeur est plus efficace lors de la recherche de la distance la plus courte, et la solution Writer est une recherche de priorité de largeur ( La recherche de priorité de profondeur chercherait trop profondément **).

answerD.py


import sys
h,w=map(int,input().split())
sys.setrecursionlimit(h*w+10)
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)

Recommended Posts

AtCoder Beginner Contest 102 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 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 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 047 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 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 083 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
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes
AtCoder Beginner Contest 106 Revue des questions précédentes
AtCoder Beginner Contest 122 Revue des questions précédentes
AtCoder Beginner Contest 125 Revue des questions précédentes
AtCoder Beginner Contest 109 Revue des questions précédentes