[PYTHON] AtCoder Débutant Contest 175 Critique
Les résultats de cette fois
Impressions de cette époque
J'ai eu une performance bleue pour la première fois depuis longtemps ... C'était la troisième performance bleue pour la première fois en 3 mois. Si vous pouvez obtenir le résultat comme vous le pouvez, vous obtiendrez autant de performance (devrait), donc je veux améliorer ma mentalité. De plus, j'ai pu passer le problème C à une vitesse assez élevée, mais en raison de ** trop m'inquiéter du classement des environs dans les problèmes D et E **, cela a pris un temps considérable, alors soyez prudent après cela je veux
Problème A
Puisqu'il n'y a que 3,2,1,0 sorties, nous avons divisé les cas dans chaque cas. Autant que je puisse voir, il semble y avoir une solution plus propre, donc je suis conscient de résoudre le problème A proprement.
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)
Problème B
Recherchez les trois côtés du triangle. Aussi, pour compter sans duplication, il faut faire range (n) → range (i + 1, n) → range (j + 1, n).
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)
Problème C
Presque déjà mentionné. Ce problème.
La valeur absolue peut être ** monotone diminuée ** au début, et l'opération est optimale, mais lorsque la valeur absolue des coordonnées devient $ d $ ou moins (cette fois est $ e $), alors * * Il est préférable d'aller et venir entre $ e $ et $ de $ **.
Par conséquent, cet aller-retour est déterminé par ** la régularité et la bizarrerie du nombre de mouvements restant **, et la réponse est $ e $ lorsque le nombre de mouvements restant en atteignant $ e $ pour la première fois est pair, et $ de $ lorsqu'il est impair. Je vais.
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])
Problème D
J'ai essayé de le mettre en œuvre avec soin tout en commentant, donc j'ai pu trouver le boîtier d'angle en douceur.
Déplacez le cadre en fonction du nombre écrit, mais si vous atteignez deux fois un certain carré, vous pouvez voir que ** le comportement après cela est le même, donc un cycle est susceptible d'apparaître **.
Aussi, nous pouvons voir ici qu'il y a toujours un cycle ** du fait de la contrainte qu'il s'agit d'une séquence séquentielle (le même numéro n'apparaît pas lors de l'enregistrement du numéro de la cellule tracée lorsqu'il n'y a pas de cycle, mais dans le cas d'une séquence séquentielle Vous pouvez voir que c'est impossible.)
En dessous, nous suivrons les cellules de chaque cellule à la suivante, mais comme $ K $ est extrêmement grand, il est nécessaire de ** calculer le cycle collectivement **. Par conséquent, vous devez d'abord ** détecter le cycle **. Il semble y avoir plusieurs méthodes, mais j'ai préparé et implémenté un tableau qui enregistre les carrés déjà tracés ** et un tableau qui enregistre l'ordre dans lequel ils ont été tracés **. Plus précisément, sélectionnez chaque cellule comme point de départ et essayez de répéter le processus jusqu'à ce que la cellule que vous avez déjà tracée apparaisse. Aussi, ** calculez d'abord la partie qui n'est pas incluse dans le cycle **, et si elle est toujours inférieure à $ K $, passez au calcul du cycle. (Étant donné que le nombre de mouvements est de 1 $ ou plus et de $ K $ ou moins, il est nécessaire de vérifier si la valeur maximale est mise à jour ** à chaque fois que la cellule est tracée.)
Tout d'abord, lorsque vous commencez à faire le tour du cycle, il y a des cas où vous ne pouvez pas faire le tour **, nous allons donc commencer par diviser les cas. Après cela, réfléchissez à l'opportunité ou non de faire le tour du cycle. Tout d'abord, calculez le score que vous obtiendrez en un tour du cycle. À ce stade, si le ** score du cycle est négatif **, il n'est pas nécessaire de passer par le cycle en premier lieu. Cependant, même si vous n'êtes pas obligé de suivre le cycle, il existe un modèle qui vous permet de mettre à jour la valeur maximale lorsque vous vous déplacez vers le milieu du cycle **, vous devez donc vérifier un tel modèle. Ensuite, si le score du ** cycle est non négatif **, il vaut mieux faire le tour du cycle, alors faites le plus possible. Et j'ai pensé que je devrais essayer de déplacer la masse pour la dernière partie restante, mais ** En fait, cette méthode produit un motif WA **. Cela signifie que même si le score total du cycle est non négatif, ** il y a des modèles où il vaut mieux ne pas tourner le dernier cycle ** (je ne montre pas ici qu'il vaut mieux tourner le non-dernier cycle). ). Par conséquent, vous pouvez suivre de tels modèles en ** pensant uniquement au dernier cycle **, et vous pouvez couvrir tous les modèles en les divisant dans les cas ci-dessus. (Ici, j'ai pu découvrir WA en me concentrant sur ** l'opportunité de faire le tour du cycle **.)
Aussi, je voudrais être prudent car le problème de modèle de ** lors de l'exécution d'opérations dans un lot est optimal mais pas optimal lorsqu'une seule partie est retirée ** est parfois vu et les erreurs sont difficiles à remarquer.
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 fois ou plus et K fois ou moins
ansF=-1000000000000000000
for i in range(n):
#Ce que vous avez déjà suivi
check=[False]*n
#L'ordre de traçage
turns=[]
#maintenant
now=i
while check[now]==False:
check[now]=True
turns.append(now)
now=p[now]
#répondre(Maintenant)
ans=0
#Combien de fois sur k
#Mettre à jour à chaque fois
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
#Durée du cycle
l=len(turns)
#Somme du cycle(Aussi)
#Où arrêter le cycle
x=0
for j in range(l):
x+=c[turns[j]]
#Si le cycle ne tourne pas en premier lieu
if spare<=l:
for j in range(spare):
ans+=c[turns[j]]
ansF=max(ans,ansF)
continue
#Parfois, il vaut mieux faire du vélo
#Certains modèles ne doivent pas être tournés dans le dernier cycle
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)
#Quand il vaut mieux ne pas faire de vélo
else:
for j in range(l):
ans+=c[turns[j]]
ansF=max(ans,ansF)
print(ansF)
E problème
Avec environ 10 minutes restantes, j'ai soumis la politique en toute confiance, puis TLE. $ R \ fois C \ fois 4 \ simeq 3,6 \ fois 10 ^ 7 $ Donc je pensais que c'était à peine possible pour PyPy, donc je l'ai réécrit avec l'intention de mourir et l'ai soumis il y a environ cinq minutes.
Tout d'abord, puisqu'il s'agit d'un problème typique, je pense qu'il est facile d'établir une politique de base. ** Problème de recherche sur la grille ** et ** La transition est claire **, et ** Nombre d'états ** semble être bon si vous enregistrez le nombre d'éléments ramassés pour chaque colonne (4 façons), DP A été établi en tant que politique. Plus précisément, il est défini comme suit.
$ dp [i] [j] [k]: = $ (Valeur totale maximale des articles lorsque le nombre d'articles sélectionnés dans la ligne est $ k $ en atteignant la masse ($ i, j $))
Il y a une transition vers le bas et une transition vers la droite, mais c'est un peu compliqué, donc une ** classification des cas ** est nécessaire. Considérons également la transition depuis l'état de $ dp [i] [j] [l]
(1) En cas de transition vers le bas
Faites une transition de masse ($ i, j
(2) En cas de transition vers la droite
Faites une transition de la masse ($ i, j
Si la transition ci-dessus est connue, DP est initialisé à 0, et si l'élément existe dans la masse ($ 0,0 $), dp [0] [0] [1] = $ item [0] [0] $ Si vous n'oubliez pas d'initialiser avec, faites simplement 3D DP.
E.cc
//Options de débogage:-fsanitize=undefined,address
//Optimisation du compilateur
#pragma GCC optimize("Ofast")
//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#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 est un conteneur tel que vector
#define ALL(x) x.begin(),x.end()
#define SIZE(x) ll(x.size())
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire
signed main(){
//Code pour accélérer la saisie
//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;
}
Problème F
J'ai eu une image de la politique en me référant à l'explication, donc je vais la résoudre dans quelques jours.
Recommended Posts