Critique du concours AtCoder

Les résultats de cette fois

スクリーンショット 2020-04-26 23.13.50.png

Impressions de cette époque

Problème A

Les observations sont classées selon que w est s ou plus.

A.py


s,w=map(int,input().split())
print("unsafe" if w>=s else "safe")

Problème B

La force physique d'Aoki est c → cb en raison de l'attaque de Takahashi, et la force physique de Takahashi est un → ad que l'attaque d'Aoki, donc comme les restrictions sont lâches, la force physique devient 0 ou moins d'abord en simulant l'attaque. Celui qui perd. Le test sauve quel tour d'attaque.

B.py


a,b,c,d=map(int,input().split())
check=True
while True:
    if check:
        c-=b
        if c<=0:
            print("Yes")
            break
    else:
        a-=d
        if a<=0:
            print("No")
            break
    check=not check

Problème C

C'est un modèle courant. Il y a plusieurs façons sans couverture, alors utilisez l'ensemble.

C.py


n=int(input())
s=set()
for i in range(n):
    s.add(input())
print(len(s))

Problème D

Si vous restez bloqué en D même pour un instant, vous vous retrouverez avec un échec comme celui-ci ... ** Vous devez avoir une bonne compréhension des problèmes typiques **. Tout d'abord, en regardant l'exemple, j'ai remarqué que ** il y a peu de modèles **, et si j'écris honnêtement toutes les chaînes de caractères de i à j, il est clair que O ($ N ^ 2 $) n'est pas suffisant **. Vous pouvez voir qu'il y en a. Sur cette base, si l'on considère le nombre $ n $ du caractère $ i $ au caractère $ j $, ** "Nombre du caractère $ i $ au dernier caractère ($ k )" à "" Je me suis souvenu qu'il y avait un ** problème similaire auquel je pensais en soustrayant le nombre du caractère j-1 $ au dernier caractère ($ l $), donc j'ai pensé qu'il pourrait être utilisé ici aussi. En d'autres termes, pour savoir si le nombre $ n $ du caractère $ i $ au caractère $ j $ est un multiple de 2019, si ** $ k, l $ sont congruents lorsque 2019 est la loi. On peut dire que (i, j) satisfait la condition ** (∵ ** 2019 vaut 2 et 5 et l'un l'autre **). Donc,xNuméro de la première lettre à la dernière lettre|S|Stocker le nombre de restes divisé par 2019 pour chaque rue dans le dictionnaire, et quand chaque reste z est y rues_yC_2alors(i,j)の組み合わせを求めることがalorsきます。このzを0~2018alors考えて和を考えれば良いのalorsすが、ここalors二つ罠があります。 Le premier piège est que cette méthode ne prend pas en compte si le nombre du caractère ** $ i $ au dernier caractère est un multiple de 2019 **. Par conséquent, nous devons ajouter les éléments tels que z est 0 comme réponse. Le deuxième piège, comme vous pouvez le voir dans le code ci-dessous, est que vous devez calculer la puissance de 10 avec la fonction pow lors du premier calcul du nombre du caractère $ x $ au dernier caractère. Cependant, puisque l'indice de ** 10 est de 200 000-1 au maximum, il faut beaucoup de temps pour calculer la puissance **. Par conséquent, ici, en introduisant la condition que ** mod est 2019 et en calculant ** (mod peut être spécifié comme troisième argument en Python), il est possible de calculer la puissance avec une petite quantité de calcul. Avec cette accélération, TLE peut être pris, et il est possible d'écrire un programme avec un temps d'exécution suffisant.

answerD.py


s=input()
l=len(s)
se=dict()
k=0
for i in range(l-1,-1,-1):
    k+=(pow(10,l-1-i,2019)*int(s[i]))
    k%=2019
    if k in se:
        se[k]+=1
    else:
        se[k]=1

ans=0
for j in se:
    i=se[j]
    if i>1:
        ans+=(i*(i-1)//2)
    if j==0:
        ans+=i
print(ans)

E problème

C'est un problème de la méthode Dyxtra étendue (j'ai remarqué la méthode Dyxtra, mais je n'ai pas pu la résoudre à temps ...). Même l'implémentation de la méthode Dyxtra de base était suspecte, donc je l'ai donnée comme résumé de la méthode Dyxtra dans Another article avec une explication de ce problème. Veuillez être là quand c'est une bonne référence. Pour le moment, je ne collerai que le code ci-dessous.

answerE.cc


//Comprendre(Ordre alphabétique,bits/stdc++.Une faction qui n'utilise pas h)
#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

using namespace std;
typedef long long ll;

//macro
//pour la relation de 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.
#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--)
//x est un conteneur tel que vector
#define ALL(x) (x).begin(),(x).end() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à ll
#define MAX(x) *max_element(ALL(x)) //Trouvez la valeur maximale
#define MIN(x) *min_element(ALL(x)) //Trouvez la valeur minimale
//constant
//La taille de ce INF est également importante(S'il est petit, ce sera WA)
#define INF 1000000000000000 //10^15:Valeur extrêmement élevée,∞
#define MOD 10000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#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

//À partir de là, un modèle

#define VL vector<ll>

//Plus grand par ordre croissant
//La comparaison vectorielle est la priorité du premier élément, le deuxième élément ...
#define PQ priority_queue<VL,vector<VL>,greater<VL>>
//Nombre maximum de pièces d'argent à avoir
#define MAXS ll(2999)


//f est l'indice du point de départ
//n est le nombre total de sommets
//s est le nombre de devises dont vous disposez en premier
//edge est l'indice et la diminution des sommets au-delà de ce côté pour le côté s'étendant à partir de chaque sommet(ou augmenter)Un tableau avec le nombre de pièces d'argent et le temps qu'il faut
vector<VL> dijkstra(ll f,ll n,ll s,vector<vector<VL>>& edge){
    //Le nombre maximum de pièces d'argent que vous possédez est MAXS
    s=min(s,MAXS);
    //Un tableau qui vérifie si le temps le plus court dans l'état du nombre de chaque devise à chaque sommet a été déterminé
    vector<VL> confirm(n,VL(MAXS+1,false));
    //Un tableau qui stocke le temps le plus court dans l'état du nombre de chaque devise à chaque sommet
    //État initial au point de départ(J'ai la devise S)Est 0, sinon INF initialise le temps le plus court
    vector<VL> mincost(n,VL(MAXS+1,INF));mincost[f][s]=0;
    //Confirmé(sommet,Nombre de devises)Le long du côté qui s'étend de l'ensemble de(sommet,Nombre de devises)File d'attente prioritaire qui économise le temps écoulé depuis l'état initial de
    PQ mincand;mincand.push({mincost[f][s],f,s});

    //Le temps le plus court peut être mis à jour lorsque l'élément mincand est nul(sommet,Nombre de devises)Indique qu'il n'y a pas d'état de
    while(!mincand.empty()){
        //Il semble atteindre la distance la plus courte(sommet,Nombre de devises)Sortez l'état de
        VL next=mincand.top();mincand.pop();
        //Déjà ça(sommet,Nombre de devises)Si le temps le plus court dans l'état de est confirmé, ignorez-le
        if(confirm[next[1]][next[2]]) continue;
        //S'il n'est pas confirmé, faites-le confirmer
        confirm[next[1]][next[2]]=true;
        //Confirmé(sommet,Nombre de devises)L'information du côté s'étendant depuis l'état de est récupérée, l est le numéro du côté
        vector<VL>& v=edge[next[1]];ll l=SIZE(v);
        REP(i,l){
            //Calculez le nombre de pièces d'argent après le déménagement. S'il dépasse MAXS, réglez-le sur MAXS.
            ll nextS=min(next[2]+v[i][1],MAXS);
            //Ne peut pas bouger si le nombre de pièces d'argent après le déplacement est inférieur à 0
            if(nextS<0) continue;
            //Il n'est pas nécessaire de mettre à jour si le temps de déplacement est plus long que le mincost à la fin du côté(Satisfaire cela lorsque la pointe du côté est confirmée)
            if(mincost[v[i][0]][nextS]<=next[0]+v[i][2]) continue;
            //mise à jour
            mincost[v[i][0]][nextS]=next[0]+v[i][2];
            //Si mis à jour, cela(sommet,Nombre de devises)L'Etat de(Pas confirmé(sommet,Nombre de devises)Dans l'état de)Peut être la distance la plus courte
            mincand.push({mincost[v[i][0]][nextS],v[i][0],nextS});
        }
    }
    return mincost;
}

signed main(){
    ll n,m,s;cin >> n >> m >> s;

    vector<vector<VL>> edge(n);
    REP(i,m){
        ll u,v,a,b;cin >> u >> v >> a >> b;
        //Ici les côtés sont bidirectionnels
        edge[u-1].PB({v-1,-a,b});
        edge[v-1].PB({u-1,-a,b});
    }
    REP(i,n){
        ll c,d;cin >> c >> d;
        //Ajouter l'opération pour augmenter la devise comme un avantage
        edge[i].PB({i,c,d});
    }
    
    vector<VL> mincost=dijkstra(0,n,s,edge);
    
    FOR(i,1,n-1) cout << MIN(mincost[i]) << endl;
}

Problème F

J'étais fatigué de l'effort d'un article à cause du problème E, donc je le résoudrai à un autre moment.

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
Critique du concours AtCoder
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
AtCoder Regular Contest 106 Évaluation
Concours AtCoder Débutant 184 Remarque
AtCoder Grand Contest 046 Critique
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