[PYTHON] Critique du concours AtCoder
Les résultats de cette fois
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
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