AtCoder Débutant Contest 175 Critique

Les résultats de cette fois

スクリーンショット 2020-08-16 10.43.50.png

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] . De plus, dans ce qui suit, la valeur de l'élément dans la masse ( i, j $) est $ item [i] [j] $.

(1) En cas de transition vers le bas Faites une transition de masse ($ i, j ) à masse ( i + 1, j $). De plus, dans la ligne $ i + 1 , seuls les éléments du carré ( i + 1, j $) peuvent être sélectionnés, donc la transition ne dépend pas de la valeur de ** $ l $ **. [1] Lorsque vous ne sélectionnez aucun élément sur le carré ($ i + 1, j $) dp[i+1][j][0]=max(dp[i+1][j][0],dp[i][j][l]) [2] Lors de la sélection d'un élément sur le carré ($ i + 1, j $) dp[i+1][j][1]=max(dp[i+1][j][1],dp[i][j][l]+item[i+1][j])

(2) En cas de transition vers la droite Faites une transition de la masse ($ i, j ) à la masse ( i, j + 1 $). De plus, dans la ligne $ i $, les éléments $ l $ sont sélectionnés, donc lorsque ** $ l = 3 , aucun élément ne peut être sélectionné **. [1] Lorsque vous ne sélectionnez pas l'élément sur le carré ( i, j + 1 $) dp[i][j+1][l]=max(dp[i][j+1][l],dp[i][j][l]) [2] Lors de la sélection d'un élément sur le carré ($ i, j + 1 $) (cependant, $ l <3 $) dp[i][j+1][1]=max(dp[i][j+1][1],dp[i][j][l]+item[i][j+1])

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

Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
Critique du concours AtCoder
AtCoder Débutant Contest 175 Critique
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 181 Remarque
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
Concours AtCoder Débutant 180 Remarque
Concours AtCoder Débutant 182 Remarque
AtCoder Grand Contest 048 Critique
Concours AtCoder pour débutants 156 WriteUp
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Concours AtCoder pour débutants 167
Concours AtCoder Débutant 183 Remarque
Concours AtCoder Débutant 184 Remarque
Revue du concours régulier AtCoder 104
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes