[PYTHON] AtCoder Beginner Contest 088 Rückblick auf frühere Fragen

Benötigte Zeit

Impressionen

Dies ist eine frühere Frage, die ich zuvor gelöst habe, aber ich habe den gleichen Fehler erneut mit dem D-Problem gemacht. Ich möchte den Inhalt des Fehlers im D-Problem erwähnen.

Problem A

Ich habe eine unendliche Anzahl von 500-Yen-Währungen. Überlegen Sie also, ob der Rest der Division von n durch 500 kleiner als a ist.

answerA1.py

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

B-Problem

Alice nimmt 0-indizierte und gerade-indizierte in absteigender Reihenfolge und Bob nimmt ungerade-indizierte, was eine Strategie ist, um ihre Punktzahlen zu maximieren.

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-Problem

Für Zeile i ist es $ a_i + b_1, a_i + b_2, a_i + b_3 $ und für jede Zeile (Wert in Spalte 2-1 Wert in Spalte 1) und Wert in Spalte 3-2. ) Sind die Bedingungen erforderlich, damit Takahashis Informationen korrekt sind, und aus Experimenten wird deutlich, dass es ausreicht, den Wert von a angemessen einzustellen, wenn diese Bedingung erfüllt ist. (Die Erklärung ist angemessen, aber es ist klar, wann Sie tatsächlich berechnen (Wert in der zweiten Spalte - Wert in der ersten Spalte) bzw. (Wert in der dritten Spalte - Wert in der zweiten Spalte).)

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 Problem

Ich erinnerte mich, wie ich dieses Problem lösen konnte, weil es beeindruckend war, es vorher zu lösen, aber am Ende habe ich viele Fehler gemacht. Sunuke möchte seine Punktzahl so weit wie möglich verbessern, daher muss er so viele Felder wie möglich in Schwarz ändern. Wenn Sie jedoch zu viele Felder ändern, können Sie das Ziel nicht erreichen. Mit anderen Worten, alles, was Sie tun müssen, ist, alles außer den Feldern auszufüllen, denen Kenusu folgt, um das Ziel zu erreichen, und ** um zu maximieren, können Sie alles außer dem kürzesten Weg ausfüllen. Daher kann dieses Problem als einfaches Problem der kürzesten Route angesehen werden. Ich habe den Code mit dfs geschrieben. Im Fall von Python wird die Obergrenze der Wiederholungstiefe jedoch von jeder Umgebung festgelegt, sodass `sys.setrecursionlimit (x)` die Wiederholungsgrenze auf x ** festlegt. .. Wenn dieses ** x jedoch zu groß ist, wird es TLE, daher sollte es so klein wie möglich sein . In diesem Problem ist H 50 und W 50, also dachte ich, es wäre gut, wenn es 2500 oder mehr wäre, aber da es RE wurde, scheint es ein Muster zu geben, bei dem die Anzahl der Wiederholungen mehr als 2500 beträgt (ich kann mir das nicht vorstellen ...) .. Ich habe versucht, die Anzahl der Wiederholungen auf das Limit zu beschränken, aber es hat aufgrund der Absicht von Writer nicht funktioniert. Am Ende habe ich es geschafft, indem ich mit ** PyPy ** beschleunigt habe. Darüber hinaus ist die Suche nach Breitenpriorität effektiver, wenn die kürzeste Entfernung gefunden wird, und die Writer-Lösung ist eine Suche nach Breitenpriorität ( Suche nach Tiefenpriorität würde zu tief suchen **).

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)