AtCoder Review of past questions (first half of 12 / 8,9)

I will keep a record of the problems that I made a mistake in the past questions of AtCoder and the problems that left an impression on me.

ABC079-D(Wall)

3RE

I made a lot of silly mistakes, so I was rushing to solve it. The basic policy is that when changing the number of $ A_ {i, j} $ to 1, it takes time to find the minimum magical power to change that number to 1, so first apply each minimum magical power to the WF method. It is a policy to ask for it using. I felt growth up to the point where I came up with the minimum magical power (while changing the numbers) → WF method, but when I rewrote it, I made a mistake in the index value and it became RE. It was. ** (I changed the place to j to i.) Furthermore, if you write like [] * n **, you will not notice that each array points to the same object **, you will make a mistake at the time of input, and it will take time to debug there. I have.

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]

#The image of the WF method is to consider the shortest time without going through others, increase the places that can be passed from there, and take min more and more.
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):
        #I made a mistake in the subscript here
        if s[j]!=-1 and s[j]!=1:
            c+=dp[s[j]][1]
print(c)

ABC088-D(Grid Repainting)

10RE or more

I was addicted to it like never before, so I learned a lot at the same time as I withered. This problem can be solved by ** thinking about the pattern that can be reached in the shortest time from the start point (1,1) to the end point (H, W) **. (It's a little difficult to come up with this idea ??) Specifically, we implemented it by going to the four adjacent squares that can be reached from the square at that time and updating the information of the squares that arrived. Also, since what we want to find is a pattern that can be reached in the shortest time, if it is not the shortest from the start point, we devised a way to reduce the amount of calculation by stopping the recursion there without updating the square information. It wasn't difficult as long as I came up with a method, but it seems that my method wasn't the best, and in Python ** recursion was too deep and it became RE **. (It was my first experience. In the case of RE, I thought it was an out-of-array reference.) I checked here ** It seems that the depth of recursion is fixed in each environment in Python **, so the `setrecursionlimit``` function of the sys module (the function that sets the depth of recursion) Was used. I defined the depth of recursion by myself with the `setrecursionlimit``` function and forced to exit when it was about to exceed that depth. Also, I didn't want to solve it with this solution, so when I rewrote it in C ++, I was able to AC without setting the depth of recursion. (Also, I learned here that you can ** a <= x <= b in Python but not in 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)
#Consideration when you cannot reach
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 Review of past questions (first half of 12 / 8,9)
AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 105 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions
AtCoder Beginner Contest 067 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 081 Review of past questions
AtCoder Beginner Contest 060 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 103 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 124 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 092 Review of past questions
AtCoder Beginner Contest 099 Review of past questions
AtCoder Beginner Contest 065 Review of past questions
AtCoder Beginner Contest 094 Review of past questions
AtCoder Beginner Contest 063 Review of past questions
AtCoder Beginner Contest 107 Review of past questions
AtCoder Beginner Contest 071 Review of past questions
AtCoder Beginner Contest 082 Review of past questions
AtCoder Beginner Contest 084 Review of past questions
AtCoder Beginner Contest 068 Review of past questions
AtCoder Beginner Contest 058 Review of past questions
AtCoder Beginner Contest 043 Review of past questions
AtCoder Beginner Contest 098 Review of past questions
AtCoder Beginner Contest 114 Review of past questions
AtCoder Beginner Contest 120 Review of past questions
AtCoder Beginner Contest 108 Review of past questions
AtCoder Beginner Contest 106 Review of past questions