Help us understand the problem. What is going on with this article?

AtCoder Beginner Contest 088 過去問復習

所要時間

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

感想

以前解いた過去問になりますが、D問題でまた同じミスをしてしまいました。
D問題にてミスの内容については言及しておきたいと思います。

A問題

500円通貨は無限に持っているので、nを500で割った余りがaより小さいかどうかを考えます。

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

B問題

大きい順に並べて0-indexedで偶数のインデックスのものをAliceがとり、奇数のインデックスのものをBobがとるのが、二人の自分の得点を最大化する戦略となります。

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)

C問題

i行目について$a_i+b_1,a_i+b_2,a_i+b_3$であり、それぞれの行について(2列目の値-1列目の値)と(3列目の値-2列目の値)はそれぞれ等しいことが高橋君の情報が正しいために必要な条件であり、この条件を満たしている時は適当にaの値を定めれば十分であることも実験をすると明らかになります。(説明が適当ですが、(2列目の値-1列目の値)と(3列目の値-2列目の値)をそれぞれ実際に計算すると明らかです。)

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")

D問題

この問題は前に解いて印象的だったので解き方は覚えていましたが、最後ミスを多発してしまいました。
すぬけ君はできるだけスコアを伸ばしたいので、できるだけ多くのマス目を黒に変える必要があります。しかし、マス目を多く変えすぎるとけぬす君がゴールにたどり着くことができません。つまり、けぬす君が辿ってゴールにいく際に通るマス目以外の全てを塗りつぶせば良く、最大化するには最短経路で通るところ以外の全てを塗りつぶせば良いです。
したがって、この問題は単純な最短経路問題とみなすことができます。僕はdfsによりコードを書きました。しかし、Pythonの場合は再帰の深さの上限がそれぞれの環境によって設定されているので、sys.setrecursionlimit(x)によって再帰の制限回数をxに設定しました。しかし、このxが大きすぎるとTLEしてしまうので、できるだけ小さくする必要があります。この問題ではHが50でWが50なので2500以上であれば良いかと思ったのですがREになってしまったので再帰回数が2500より多くなるパターンがあるようです(パッと思いつきません…)。
再帰回数をギリギリに設定しようとしましたが、Writerの意向なのかうまくいきませんでした。ここで最後にPyPyで高速化することでうまくいきました。また、最短距離を求める際には幅優先探索の方が有効でWriter解は幅優先探索になります(深さ優先探索だと余計に深く調べ過ぎてしまうので)。

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)
DaikiSuyama
PythonとC++で競技プログラミングをしています(highest:AtCoder:1413,Codeforces:1672)。 機械学習も少し勉強しています。 FXや株の自動売買、音楽の自動生成に興味があります。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away