AtCoder Revue des questions précédentes (première moitié de 12 / 8,9)

Je garderai une trace des problèmes que j'ai commis une erreur dans les questions passées d'AtCoder et des problèmes qui m'ont marqué.

ABC079-D(Wall)

3RE

J'ai fait beaucoup d'erreurs stupides, alors je me dépêchais de le résoudre. La politique de base est que lors du changement du nombre de $ A_ {i, j} $ à 1, il faut du temps pour trouver la puissance magique minimale pour changer ce nombre à 1, alors appliquez d'abord chaque puissance magique minimale à la méthode WF. C'est une politique de le demander en utilisant. J'ai ressenti une croissance au point où j'ai trouvé le pouvoir magique minimum (en changeant les nombres) → Méthode WF, mais quand je l'ai réécrit, j'ai fait une erreur dans la valeur d'index et c'est devenu RE. C'était. ** (J'ai changé l'endroit en j en i.) De plus, si vous écrivez comme [] * n **, vous ne remarquerez pas que chaque tableau pointe vers le même objet **, vous ferez une erreur au moment de la saisie, et il faudra du temps pour y déboguer. J'ai.

answerD.py


dp=[[0 for j in range(10)] for i in range(10)]

h,w=map(int,input().split())
for i in range(10):
    s=list(map(int,input().split()))
    for j in range(10):
        dp[i][j]=s[j]

#L'image de la méthode WF est de considérer le temps le plus court sans passer par d'autres, d'augmenter les places qui peuvent être passées à partir de là, et de prendre des min de plus en plus.
for k in range(10):
    for i in range(10):
        for j in range(10):
            dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])

c=0
for i in range(h):
    s=list(map(int,input().split()))
    for j in range(w):
        #J'ai fait une erreur dans l'indice ici
        if s[j]!=-1 and s[j]!=1:
            c+=dp[s[j]][1]
print(c)

ABC088-D(Grid Repainting)

10RE ou plus

J'étais accro comme jamais auparavant, alors j'ai beaucoup appris en même temps que je me fanais. Ce problème peut être résolu en ** réfléchissant au modèle qui peut être atteint dans le temps le plus court entre le point de départ (1,1) et le point final (H, W) **. (C'est un peu difficile de trouver cette idée ??) Plus précisément, nous l'avons implémenté en accédant aux quatre carrés adjacents qui peuvent être atteints à partir du carré à ce moment-là et en mettant à jour les informations des carrés arrivés. Aussi, comme ce que nous voulons trouver est un modèle qui peut être atteint dans les plus brefs délais, s'il n'est pas le plus court depuis le point de départ, nous avons imaginé un moyen de réduire la quantité de calcul en arrêtant la récurrence là-bas sans mettre à jour les informations des carrés. Cela n'a pas été difficile tant que j'ai trouvé une méthode, mais il semble que ma méthode n'était pas la meilleure, et en Python ** la récursivité était trop profonde et elle est devenue RE **. (C'était ma première expérience. Dans le cas de RE, je pensais que c'était une référence hors service.) Quand j'ai vérifié ici, il semblait que ** en Python, la profondeur de récurrence est fixée dans chaque environnement **, donc la fonction setrecursionlimit '' du module sys (la fonction qui définit la profondeur de récurrence) A été utilisé. J'ai défini moi-même la profondeur de récurrence avec la fonction setrecursionlimit '' et forcé de quitter quand il était sur le point de dépasser cette profondeur. De plus, je ne voulais pas le résoudre avec cette solution, donc lorsque je l'ai réécrit en C ++, j'ai pu AC sans définir la profondeur de récurrence. (De plus, j'ai appris ici que vous pouvez ** a <= x <= b en Python mais pas en C ++ **.)

answerD.py


import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if I<h-1:
        if x[I+1][J]=="." and dp[I+s1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
#Prise en compte lorsque vous ne pouvez pas atteindre
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])

answerD.cc


#include<iostream>
#include<vector>
#include<string>

using namespace std;
typedef vector< vector<int> > vv;
#define INF 1e9

void go_next(int I,int J,vv& dp,vector<string> x,int w,int h){
  if(I<h-1){
    if(x[I+1][J]=='.' and dp[I+1][J]>dp[I][J]+1){
      dp[I+1][J]=dp[I][J]+1;go_next(I+1,J,dp,x,w,h);
    }
  }
  if(0<I){
    if(x[I-1][J]=='.' and dp[I-1][J]>dp[I][J]+1){
      dp[I-1][J]=dp[I][J]+1;go_next(I-1,J,dp,x,w,h);
    }
  }
  if(J<w-1){
    if(x[I][J+1]=='.' and dp[I][J+1]>dp[I][J]+1){
      dp[I][J+1]=dp[I][J]+1;go_next(I,J+1,dp,x,w,h);
    }
  }
  if(0<J){
    if(x[I][J-1]=='.' and dp[I][J-1]>dp[I][J]+1){
      dp[I][J-1]=dp[I][J]+1;go_next(I,J-1,dp,x,w,h);
    }
  }
}

int main(){
  int h ,w;cin >> h >> w;
  vv dp(h,vector<int>(w,INF));dp[0][0]=1;
  vector<string> x(h);for(int i=0;i<h;i++)cin >>x[i];
  int c=0;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(x[i][j]=='.'){c+=1;}
    }
  }
  go_next(0,0,dp,x,w,h);
  if(dp[h-1][w-1]==INF)cout << -1 << endl;
  else cout << c-dp[h-1][w-1] << endl;
}

Recommended Posts

AtCoder Revue des questions précédentes (première moitié de 12 / 8,9)
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 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 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 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 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 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 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 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