[PYTHON] AtCoder Anfängerwettbewerb 175 Bewertung
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich habe zum ersten Mal seit langer Zeit eine blaue Aufführung bekommen ... Es war die dritte blaue Aufführung zum ersten Mal seit 3 Monaten. Wenn Sie das Ergebnis so gut wie möglich erzielen können, erhalten Sie so viel Leistung (sollten), dass ich meine Mentalität verbessern möchte. Ich war auch in der Lage, das C-Problem mit einer ziemlich hohen Geschwindigkeit zu überwinden, aber aufgrund der ** übermäßigen Sorge um die Rangfolge der Umgebung bei den D- und E-Problemen ** dauerte es eine beträchtliche Zeit, also seien Sie danach vorsichtig ich will
Problem A
Da es nur 3,2,1,0 Ausgänge gibt, haben wir die Fälle jeweils aufgeteilt. Soweit ich sehen kann, scheint es eine sauberere Lösung zu geben, daher bin ich mir bewusst, Problem A ordentlich zu lösen.
A.py
s=input()
if s=="RRR":
print(3)
elif s=="RRS" or s=="SRR":
print(2)
elif s=="SSS":
print(0)
else:
print(1)
B-Problem
Durchsuche alle drei Seiten des Dreiecks. Um ohne Duplizierung zu zählen, ist es außerdem erforderlich, "Bereich (n)" → "Bereich (i + 1, n)" → "Bereich (j + 1, n)" festzulegen.
B.py
n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n):
for j in range(i+1,n):
for k in range(j+1,n):
if l[i]+l[j]>l[k] and l[i]!=l[j] and l[j]!=l[k]:
ans+=1
print(ans)
C-Problem
Fast schon erwähnt. Dieses Problem.
Der Absolutwert kann zu Beginn ** monoton verringert ** werden, und die Operation ist optimal, aber wenn der Absolutwert der Koordinaten $ d $ oder weniger wird (diesmal $ e $), dann * * Es ist am besten, zwischen $ e $ und $ de $ hin und her zu gehen **.
Daher wird diese Rundreise durch die Gleichmäßigkeit und Seltsamkeit der verbleibenden Anzahl von Bewegungen ** bestimmt, und die Antwort lautet $ e $, wenn die verbleibende Anzahl von Bewegungen beim ersten Erreichen von $ e $ gerade ist, und $ de $, wenn sie ungerade ist. Ich werde.
C.py
x,k,d=map(int,input().split())
x=abs(x)
if x>k*d:
print(x-k*d)
else:
k-=x//d
x-=(d*(x//d))
ans=[x,abs(d-x)]
print(ans[k%2])
D Problem
Ich habe versucht, es beim Auskommentieren sorgfältig umzusetzen, damit ich den Eckfall reibungslos finden konnte.
Bewegen Sie den Rahmen entsprechend der geschriebenen Zahl. Wenn Sie jedoch zweimal ein bestimmtes Quadrat erreichen, können Sie sehen, dass ** das Verhalten danach dasselbe ist, sodass wahrscheinlich ein Zyklus auftritt **.
Auch hier können wir sehen, dass es immer einen Zyklus ** aus der Einschränkung gibt, dass es sich um eine sequentielle Sequenz handelt (dieselbe Nummer erscheint nicht, wenn die Anzahl der Quadrate aufgezeichnet wird, die verfolgt werden, wenn kein Zyklus vorhanden ist, sondern im Fall einer sequentiellen Sequenz Sie können sehen, dass es unmöglich ist.)
Darunter folgen wir den Zellen von einer Zelle zur nächsten, aber da $ K $ extrem groß ist, ist es notwendig, ** den Zyklus gemeinsam zu berechnen **. Daher müssen Sie zuerst ** den Zyklus erkennen **. Es scheint verschiedene Methoden zu geben, aber ich habe ein Array vorbereitet und implementiert, das die bereits verfolgten Quadrate aufzeichnet ** und ein Array, das die Reihenfolge aufzeichnet, in der sie verfolgt wurden **. Wählen Sie insbesondere jede Zelle als Ausgangspunkt aus und versuchen Sie, den Vorgang zu wiederholen, bis die bereits verfolgte Zelle angezeigt wird. ** Berechnen Sie zuerst den Teil, der nicht im Zyklus enthalten ist **, und fahren Sie mit der Zyklusberechnung fort, wenn er immer noch weniger als $ K $ beträgt. (Da die Anzahl der Bewegungen $ 1 $ oder mehr und $ K $ oder weniger beträgt, muss jedes Mal, wenn die Zelle verfolgt wird, überprüft werden, ob der Maximalwert ** aktualisiert wird.)
Wenn Sie anfangen, den Zyklus zu durchlaufen, gibt es Fälle, in denen Sie nicht umgehen können **, daher werden wir die Fälle zuerst klassifizieren. Überlegen Sie danach, ob Sie den Zyklus durchlaufen möchten oder nicht. Berechnen Sie zunächst die Punktzahl, die Sie in einer Runde des Zyklus erhalten. Wenn zu diesem Zeitpunkt die ** Zyklusbewertung negativ ist **, besteht keine Notwendigkeit, den Zyklus überhaupt erst zu durchlaufen. Selbst wenn Sie den Zyklus nicht durchlaufen müssen, gibt es ein Muster, das den Maximalwert aktualisieren kann, wenn Sie sich in der Mitte des Zyklus befinden **. Daher müssen Sie ein solches Muster überprüfen. Wenn die Punktzahl des Zyklus nicht negativ ist **, ist es besser, den Zyklus zu durchlaufen, also gehen Sie so viel wie möglich herum. Und ich dachte, ich sollte versuchen, die Masse für den letzten verbleibenden Teil zu verschieben, aber ** Tatsächlich erzeugt diese Methode ein WA-Muster **. Dies bedeutet, dass selbst wenn die Gesamtpunktzahl des Zyklus nicht negativ ist, ** es Muster gibt, in denen es besser ist, den letzten Zyklus nicht zu drehen ** (ich zeige hier nicht, dass es besser ist, den nicht letzten Zyklus zu drehen). ). Daher können Sie solchen Mustern folgen, indem Sie ** nur an den letzten Zyklus denken **, und Sie können alle Muster in den oben genannten Fällen abdecken. (Hier konnte ich WA entdecken, indem ich darauf achtete, ob ich den Zyklus umgehen sollte.)
Außerdem möchte ich vorsichtig sein, da das Musterproblem von ** bei der Ausführung von Vorgängen in einer Charge optimal, aber nicht optimal ist, wenn nur ein Teil herausgenommen wird ** manchmal auftritt und Fehler schwer zu bemerken sind.
D.py
n,k=map(int,input().split())
#0-indexed
p=[i-1 for i in list(map(int,input().split()))]
c=list(map(int,input().split()))
#1 Mal oder mehr und K Mal oder weniger
ansF=-1000000000000000000
for i in range(n):
#Was du schon verfolgt hast
check=[False]*n
#Die Reihenfolge der Rückverfolgung
turns=[]
#jetzt
now=i
while check[now]==False:
check[now]=True
turns.append(now)
now=p[now]
#Antworten(Jetzt)
ans=0
#Wie oft von k
#Jedes Mal aktualisieren
spare=turns.index(now)
if spare>=k:
for j in range(k):
ans+=c[turns[j]]
ansF=max(ans,ansF)
continue
for j in range(spare):
ans+=c[turns[j]]
ansF=max(ans,ansF)
turns=turns[spare:]
spare=k-spare
#Zykluslänge
l=len(turns)
#Zyklus Summe(Zu)
#Wo kann man den Zyklus stoppen?
x=0
for j in range(l):
x+=c[turns[j]]
#Wenn sich der Zyklus überhaupt nicht dreht
if spare<=l:
for j in range(spare):
ans+=c[turns[j]]
ansF=max(ans,ansF)
continue
#Manchmal ist es besser zu radeln
#Einige Muster sollten im letzten Zyklus nicht gedreht werden
if x>=0:
ans+=(x*(spare//l-1))
ansF=max(ans,ansF)
for j in range(l):
ans+=c[turns[j]]
ansF=max(ans,ansF)
for j in range(spare%l):
ans+=c[turns[j]]
ansF=max(ans,ansF)
#Wenn es besser ist, nicht zu radeln
else:
for j in range(l):
ans+=c[turns[j]]
ansF=max(ans,ansF)
print(ansF)
E Problem
Etwa 10 Minuten vor dem Ende reichte ich die Richtlinie mit Vertrauen ein und dann TLE. $ R \ times C \ times 4 \ simeq 3.6 \ times 10 ^ 7 $, also dachte ich, dass es für PyPy kaum möglich ist, also habe ich es mit der Absicht des Sterbens umgeschrieben und es vor ungefähr fünf Minuten eingereicht.
Da es sich um ein typisches Problem handelt, halte ich es zunächst für einfach, eine grundlegende Richtlinie festzulegen. ** Suchproblem im Raster ** und ** Der Übergang ist klar **, ** Anzahl der Zustände ** Es scheint gut, die Anzahl der für jede Spalte aufgenommenen Elemente zu speichern (4 Möglichkeiten), DP Wurde als Politik etabliert. Insbesondere wird es wie folgt eingestellt.
$ dp [i] [j] [k]: = $ (Maximaler Gesamtwert der Elemente, wenn die Anzahl der in der Zeile ausgewählten Elemente $ k $ beträgt, wenn die Masse erreicht wird ($ i, j $))
Es gibt einen Übergang nach unten und einen Übergang nach rechts, der jedoch etwas kompliziert ist, sodass eine ** Fallklassifizierung ** erforderlich ist. Betrachten Sie auch den Übergang vom Zustand von $ dp [i] [j] [l]
(1) Im Falle eines Abwärtsübergangs
Machen Sie einen Übergang von Masse ($ i, j
(2) Beim Übergang nach rechts
Machen Sie einen Übergang von Masse ($ i, j
Wenn der obige Übergang bekannt ist, wird DP auf 0 initialisiert, und wenn das Element in der Masse ($ 0,0 $) vorhanden ist, ist dp [0] [0] [1] = $ Element [0] [0] $ Wenn Sie nicht vergessen, mit zu initialisieren, führen Sie einfach 3D DP aus.
E.cc
//Debug-Optionen:-fsanitize=undefined,address
//Compileroptimierung
#pragma GCC optimize("Ofast")
//Einschließen usw.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//Makro
//für Schleife
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden um 1 dekrementiert.
//FORA ist ein Bereich für Aussagen(Wenn es schwer zu bedienen ist, löschen Sie es)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x ist ein Container wie ein Vektor
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//Konstante
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays
//Abkürzung
#define PB push_back //Einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll r,c,k;cin>>r>>c>>k;
vector<vector<ll>> item(r,vector<ll>(c,0));
REP(i,k){
ll x,y,z;cin>>x>>y>>z;
item[x-1][y-1]=z;
}
vector<vector<vector<ll>>> dp(r,vector<vector<ll>>(c,vector<ll>(4,0)));
if(item[0][0]>0)dp[0][0][1]=item[0][0];
REP(i,r){
REP(j,c){
REP(l,4){
if(l<3){
if(i!=r-1){
dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][l]);
if(item[i+1][j]>0)dp[i+1][j][1]=max(dp[i+1][j][0],dp[i][j][l])+item[i+1][j];
}
if(j!=c-1){
dp[i][j+1][l]=max(dp[i][j+1][l],dp[i][j][l]);
if(item[i][j+1]>0)dp[i][j+1][l+1]=max(dp[i][j+1][l+1],dp[i][j][l]+item[i][j+1]);
}
}else{
if(i!=r-1){
dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][l]);
if(item[i+1][j]>0)dp[i+1][j][1]=max(dp[i+1][j][0],dp[i][j][l])+item[i+1][j];
}
if(j!=c-1){
dp[i][j+1][l]=max(dp[i][j+1][l],dp[i][j][l]);
}
}
}
}
}
cout<<*max_element(ALL(dp[r-1][c-1]))<<endl;
}
F Problem
Ich habe mir anhand der Erklärung ein Bild von der Richtlinie gemacht, daher werde ich sie innerhalb weniger Tage lösen.
Recommended Posts