[PYTHON] Journal de dévotion professionnel compétitif 15e au 17e jours (7/9 au 7/11)
<! - Modèle de dévotion professionnelle compétitive->
Impressions
Je suis désolé de ne pas avoir pu résoudre ABC172-F Unfair Nim. De plus, le concours de classe ABC d'hier a été un tournant regrettable, donc je suis déçu. Récemment, j'ai été frustré par les professionnels de la compétition, mais je veux grandir sur cette base.
Jour 15
Résolu Intervalles ABC173-F sur l'arbre. Cet article explique.
16e jour
Temps pris
Environ 40 minutes (20 minutes de lecture erronée ...)
Considération
Je voulais résoudre ABC172-F Unfair Nim, mais je pouvais enfin le comprendre après avoir vu la distribution des explications et il semblait que cela prendrait du temps à mettre en œuvre. Je pense donc à le résoudre demain. (Comme cela semble difficile à mettre en œuvre, je vais l'ignorer une fois.)
C'est un diff bleu, mais je suis content d'avoir pu le passer. Cependant, je l'ai mal lu et je l'ai utilisé pendant 20 minutes, donc je veux faire attention à ne pas le faire à l'avenir.
Je pense que c'est un problème simple tant que vous avez une idée.
Tout d'abord, sélectionnez $ (i, j) $ et ajoutez +1 à $ A_i $ et -1 à $ A_j $, mais ** cette opération ne change pas la somme ** (** invariant **) !) Non. De plus, si la valeur maximale pouvant être divisée après l'opération est $ X $ et la valeur de la colonne numérique à ce moment est $ C_i = X \ fois B_i $, la formule suivante est établie. (Au fait, j'ai mal lu que $ A_i $ n'a que +1.)
En d'autres termes, $ X $ est une fraction ** positive ** de $ A_1 + A_2 +… + A_n $, donc au plus $ \ sqrt {n} $. De plus, pour chaque $ X $, le nombre minimum de fois (✳︎) pour opérer sur la colonne numérique $ A $ et le changer en colonne numérique $ C $ doit être inférieur à $ k $. Ici, afin de minimiser le nombre de fois, il est nécessaire de faire apparaître $ X \ fois B_i $ aussi près que possible de $ A_i $ (1) ** et ** le nombre total de fois +1 et -1. Doit être égal (2) **.
Selon (1), si un nombre est aussi proche que possible d'un multiple de $ X $ (** $ ceil (A_i / X) \ times X $ ou $ floor (A_i / X) \ times X $ **) Il est considéré comme bon, mais cette fois, (2) n'est pas satisfait lorsque le modèle est le suivant.
Par conséquent, supposons d'abord que chaque $ A_i $ est $ ceil (\ frac {A_i} {X}) \ times X $ (** Il est important de le supposer et de le transformer pour votre commodité !) .. À ce moment, de $ A_i-ceil (\ frac {A_i} {X}) \ times X \ geqq 0 $, $ \ sum_ {i = 1} ^ {n} (A_i-ceil (\ frac {A_i} {X} ) \ fois X) \ geqq 0 $. De même, puisque $ \ sum_ {i = 1} ^ {n} (A_i-B_i \ times X) = 0 $, $ \ sum_ {i = 1} ^ {n} (A_i-ceil (\ frac {A_i} { X}) \ times X)> If 0 $, $ ceil (\ frac {A_i} {X}) dans $ A_i $ $ floor (\ frac {A_i} {X}) \ au lieu de \ times X $ Il peut être préférable de passer aux temps X $. De plus, $ A_i-ceil (\ frac {A_i} {X}) \ times X -X = A_i-floor (\ frac {A_i} {X}) \ times X $ tient, donc ** $ A_i-ceil ( $ A_i-ceil ( \ frac {A_i} {X}) \ times Passez du plus grand X $ à $ -X $ **… (1) et changez-le en $ A_i-floor (\ frac {A_i} {X}) \ times X $ Que $ \ sum_ {i = 1} ^ {n} (A_i- (ceil (\ frac {A_i} {X}) \ \ ou \ \ floor (\ frac {A_i} {X})) \ times X) Faites jusqu'à = 0 $ et comptez le nombre de +1 (le même que le nombre de -1) à ce moment-là est (✳︎), et (✳︎) est le plus grand $ X parmi $ k $ ou moins. Demandez simplement $.
(1)… $ A_i-ceil (\ frac {A_i} {X}) \ times Il est facile de montrer intuitivement que l'opération de $ -X $ à partir de celui avec le plus grand X $ est la meilleure, donc je ne la montrerai pas ici. (** Montrez simplement que les autres options ne sont pas optimales **, ce qui est une idée importante dans la cupidité).
<détails> 1 heure 5 minutes Il m'a fallu beaucoup de temps pour bogue la bibliothèque après avoir élaboré la politique, mais je pense que je ne la bifferai plus parce que je l'ai beaucoup organisée. Je pensais utiliser BFS pour suivre, mais ** il est clair que le résultat changera en fonction du nombre de côtés que vous passez **, alors ** utilisez des pièces $ P $ lors du passage de chaque côté. Comme **, je pensais que je recevrais des pièces $ C_i-P $ en passant par le côté $ i $ ème. Par conséquent, dans ce qui suit, nous considérerons le nombre de pièces que vous pouvez obtenir au maximum en passant du sommet $ 1 $ au sommet $ N $, en supposant que vous recevrez des pièces $ C_i-P $ du côté $ i $ ème. .. Ici, si le signe de la pièce obtenue de chaque côté est inversé et que la pièce est considérée comme une distance, la distance du $ i $ ème côté se déplace du sommet $ 1 $ au sommet $ N $ à $ P-C_i $. Vous pouvez penser au problème d'itinéraire le plus court (point de départ unique). Puisque $ P-C_i $ peut être négatif, nous utilisons la méthode de Bellmanford (** inverser le signe et considérer le minimum au lieu du maximum ** le modèle doit être compris comme un exemple typique). De plus, il peut y avoir un chemin fermé négatif dans un graphe où le poids du côté est négatif , et dans ce problème, lorsqu'il y a un chemin fermé négatif qui inclut le sommet $ N $, le chemin le plus court est Il ne convient pas car il n'est pas fixe. Les chemins fermés négatifs sont inclus dans le graphique s'il existe des sommets dont le chemin le plus court est mis à jour lorsque la boucle de la méthode de Bellmanford est extraite. ( Je vais bientôt vous donner un article récapitulatif de la méthode Bellmanford **, veuillez donc vous y référer également.) Ici, je voudrais montrer l'existence d'un chemin fermé négatif qui inclut le sommet $ N $, mais il existe une ** solution menteur ** qui a tendance à tomber ([article de hamayanhamayan](https: //www.hamayanhamayan). .com / entrée / 2019/08/14/131 217)). Pour éviter cette méthode de résolution de mensonge, utilisez BFS ou DFS pour tracer les sommets qui peuvent être atteints à partir des sommets où le chemin le plus court est mis à jour lorsque la boucle de la méthode Bellmanford est à nouveau activée * * (Dans mon code, je le fais dans une fonction appelée bfs). La solution obtenue à partir de ce qui précède est
(1) Lorsqu'il n'est pas possible d'atteindre du sommet 1 au sommet N → Sortie -1
(2) Si vous pouvez atteindre le sommet N à partir du sommet 1 et qu'il y a un chemin fermé négatif incluant le sommet $ N $ → Sortie -1
(3) Lorsqu'il atteint du sommet 1 au sommet N et qu'il n'y a pas de chemin fermé négatif incluant le sommet $ N $ → Sortie du plus grand de moins et 0 de la distance la plus courte
Ce sera. ABC061-D Score Attack
Mon article de commentaire <détails>
Recommended Posts
abc136e.py
def make_divisors(n):
divisors=[]
for i in range(1,int(n**0.5)+1):
if n%i==0:
divisors.append(i)
if i!=n//i:
divisors.append(n//i)
#Si vous souhaitez trier par ordre décroissant de réduction
divisors.sort(reverse=True)
return divisors
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in make_divisors(sum(a)):
x=[a[j]-(a[j]//i)*i for j in range(n)]
x.sort(reverse=True)
s=sum(x)
compk=0
for j in range(n):
if s==0:
break
else:
s-=i
x[j]-=i
compk+=abs(x[j])
if compk<=k:
print(i)
break
Jour 17
Temps pris
Considération
Similaire
abc137e.cc
//Pour l'optimisation du compilateur
#pragma GCC optimize("O3")
//Comprendre(Ordre alphabétique)
#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
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //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
#define Umap unordered_map
#define Uset unordered_set
struct Edge{
ll to_Node;
ll cost;
Edge(ll t,ll c){to_Node=t;cost=c;}
};
vector<ll> mincost;
vector<vector<Edge>> Edges;
vector<bool> ncycle;
deque<ll> bfsrec;
//Détection négative des routes fermées
void bfs(){
ll s=SIZE(bfsrec);
REP(i,s){
ll now=*bfsrec.begin();
bfsrec.pop_front();
REP(i,SIZE(Edges[now])){
if(ncycle[Edges[now][i].to_Node]==false){
ncycle[Edges[now][i].to_Node]=true;
bfsrec.PB(Edges[now][i].to_Node);
}
}
}
if(s)bfs();
}
bool bellmanford(ll n){
//(l1-1)(Groom ordinaire)+1(détection)
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
if(mincost[j]!=INF){
ll e=Edges[j].size();
for(ll k=0;k<e;k++){
ll new_mincost=mincost[j]+Edges[j][k].cost;
if(mincost[Edges[j][k].to_Node]>new_mincost){
mincost[Edges[j][k].to_Node]=new_mincost;
if(i==n-1){
ncycle[Edges[j][k].to_Node]=true;//Vrai s'il y a une fermeture négative
bfsrec.PB(Edges[j][k].to_Node);
}
}
}
}
}
}
bfs();
if(ncycle[n-1]==true)return true;
return false;//Faux s'il n'y a pas de clôture négative incluant N
}
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n,m,p;cin>>n>>m>>p;
mincost.resize(n);mincost[0]=0;
FOR(i,1,n-1)mincost[i]=INF;
Edges.resize(n);
ncycle.resize(n);
REP(i,n)ncycle[i]=false;
//Moins le coût de p et l'inverse
REP(i,m){
ll a,b,c;cin>>a>>b>>c;
Edges[a-1].PB(Edge(b-1,p-c));
//cout<<p-c<<endl;
}
//Considérez le minimum sous ceci
bool check=bellmanford(n);
if(check or mincost[n-1]==INF){
cout<<-1<<endl;
}else{
cout<<max(-mincost[n-1],ll(0))<<endl;
}
}