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

Benötigte Zeit

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

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)

Recommended Posts

AtCoder Beginner Contest 102 Rückblick auf frühere Fragen
AtCoder Beginner Contest 085 Rückblick auf frühere Fragen
AtCoder Beginner Contest 062 Rückblick auf frühere Fragen
AtCoder Beginner Contest 113 Rückblick auf frühere Fragen
AtCoder Beginner Contest 074 Rückblick auf frühere Fragen
AtCoder Beginner Contest 051 Rückblick auf frühere Fragen
AtCoder Beginner Contest 119 Rückblick auf frühere Fragen
AtCoder Beginner Contest 151 Rückblick auf frühere Fragen
AtCoder Beginner Contest 075 Rückblick auf frühere Fragen
AtCoder Beginner Contest 054 Rückblick auf frühere Fragen
AtCoder Beginner Contest 110 Rückblick auf frühere Fragen
AtCoder Beginner Contest 117 Rückblick auf frühere Fragen
AtCoder Beginner Contest 070 Rückblick auf frühere Fragen
AtCoder Beginner Contest 105 Rückblick auf frühere Fragen
AtCoder Beginner Contest 112 Rückblick auf frühere Fragen
AtCoder Beginner Contest 076 Rückblick auf frühere Fragen
AtCoder Beginner Contest 089 Rückblick auf frühere Fragen
AtCoder Beginner Contest 069 Rückblick auf frühere Fragen
AtCoder Beginner Contest 079 Rückblick auf frühere Fragen
AtCoder Beginner Contest 056 Rückblick auf frühere Fragen
AtCoder Beginner Contest 087 Rückblick auf frühere Fragen
AtCoder Beginner Contest 093 Rückblick auf frühere Fragen
AtCoder Beginner Contest 046 Rückblick auf frühere Fragen
AtCoder Beginner Contest 123 Überprüfung früherer Fragen
AtCoder Beginner Contest 049 Rückblick auf frühere Fragen
AtCoder Beginner Contest 078 Rückblick auf frühere Fragen
AtCoder Beginner Contest 047 Rückblick auf frühere Fragen
AtCoder Beginner Contest 104 Rückblick auf frühere Fragen
AtCoder Beginner Contest 057 Rückblick auf frühere Fragen
AtCoder Beginner Contest 121 Rückblick auf frühere Fragen
AtCoder Beginner Contest 090 Rückblick auf frühere Fragen
AtCoder Beginner Contest 103 Rückblick auf frühere Fragen
AtCoder Beginner Contest 061 Rückblick auf frühere Fragen
AtCoder Beginner Contest 083 Rückblick auf frühere Fragen
AtCoder Beginner Contest 124 Rückblick auf frühere Fragen
AtCoder Beginner Contest 116 Rückblick auf frühere Fragen
AtCoder Beginner Contest 097 Rückblick auf frühere Fragen
AtCoder Beginner Contest 088 Rückblick auf frühere Fragen
AtCoder Beginner Contest 092 Rückblick auf frühere Fragen
AtCoder Beginner Contest 099 Rückblick auf frühere Fragen
AtCoder Beginner Contest 065 Rückblick auf frühere Fragen
AtCoder Beginner Contest 053 Rückblick auf frühere Fragen
AtCoder Beginner Contest 094 Rückblick auf frühere Fragen
AtCoder Beginner Contest 063 Rückblick auf frühere Fragen
AtCoder Beginner Contest 107 Rückblick auf frühere Fragen
AtCoder Beginner Contest 071 Rückblick auf frühere Fragen
AtCoder Beginner Contest 064 Rückblick auf frühere Fragen
AtCoder Beginner Contest 082 Rückblick auf frühere Fragen
AtCoder Beginner Contest 084 Rückblick auf frühere Fragen
AtCoder Beginner Contest 068 Rückblick auf frühere Fragen
AtCoder Beginner Contest 043 Rückblick auf frühere Fragen
AtCoder Beginner Contest 098 Rückblick auf frühere Fragen
AtCoder Beginner Contest 114 Rückblick auf frühere Fragen
AtCoder Beginner Contest 045 Rückblick auf frühere Fragen
AtCoder Beginner Contest 120 Rückblick auf frühere Fragen
AtCoder Beginner Contest 108 Rückblick auf frühere Fragen
AtCoder Beginner Contest 106 Rückblick auf frühere Fragen
AtCoder Beginner Contest 122 Rückblick auf frühere Fragen
AtCoder Beginner Contest 125 Rückblick auf frühere Fragen
AtCoder Beginner Contest 109 Rückblick auf frühere Fragen