[PYTHON] AtCoder Beginner Contest 065 Revue des questions précédentes

Questions passées résolues pour la première fois

Temps requis

Problème A

answerA.py

x,a,b=map(int,input().split())
if b<=a:
    print("delicious")
elif b<=a+x:
    print("safe")
else:
    print("dangerous")

Avec l'opérateur ternaire

answerA_better.py

x,a,b=map(int,input().split())
print("delicious" if b<=a else ("safe" if b<=a+x else "dangerous"))

Problème B

Connectez les brillants dans l'ordre. Je remplissais AtCoder avec B au tout début, et j'ai senti une croissance quand j'ai vu que ce n'était pas bien fait à ce moment-là.

answerB.py

n=int(input())
a=[int(input())-1 for i in range(n)]
now=0
x=[0]*n
i=0
while x[now]==0:
    i+=1
    x[now]=1
    now=a[now]
    if now==1:
        print(i)
        break
else:
    print(-1)

Problème C

J'ai fait un tableau de coefficients binomiaux, mais je n'en avais pas besoin.

answerC.cc

#include<iostream>
using namespace std;
typedef long long ll;

const int MAX = 10000000;
//Par quoi diviser
const int MOD = 1000000007;

ll fac[MAX], finv[MAX], inv[MAX];

//Prétraitement pour faire une table
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

//Calcul du coefficient binaire
ll COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(){
  //Prétraitement
  COMinit();
  int n,m;cin >> n >> m;
  if(n-m==1 or n-m==-1){
    cout << ((fac[n]%MOD)*fac[m])%MOD << endl;
  }else if(n==m){
    cout << (((fac[n]%MOD)*fac[m])%MOD*2)%MOD << endl;
  }else{
    cout << 0 << endl;
  }
}

Problème D

Quand je l'ai vu pour la première fois, je ne savais pas vraiment quoi faire (car la méthode que je pensais était susceptible d'être TLE). En regardant la réponse, il semble que l'arborescence de la superficie totale minimale soit utilisée, alors quand je l'ai étudié, j'ai trouvé qu'il y avait deux méthodes, la méthode prim et la méthode claspal. Ce dernier dit d'utiliser UnionFind, et UnionFind n'est pas très familier (j'ai oublié de l'implémenter car je l'ai trop utilisé, je dois faire avancer le livre en spirale rapidement), donc quand j'essaye de l'implémenter avec la méthode prim, beaucoup de bugs se produisent. J'ai fondu un bon bout de temps. (** L'implémentation de Priority_queue a tendance à être boguée et oublie que pousser peut changer le haut **) La méthode prim est un algorithme assez similaire à la méthode Dyxtra. Dans la méthode Dyxtra, un point de départ est déterminé et le sommet le plus proche pouvant être atteint à partir de ce point de départ est défini comme le prochain sommet à visiter, et par la suite, les visites sont répétées dans l'ordre à partir du point de départ qui peut être atteint à partir du sommet inclus dans l'ensemble de vertex visité. Je vais. En d'autres termes, préparez un tableau avec des informations sur les (multiples) arêtes s'étendant à partir de chaque sommet, extrayez uniquement les arêtes s'étendant à partir du sommet visité et plongez dans priority_queue. Ensuite, parmi les sommets non visités qui peuvent être atteints via l'arête qui plonge dans la priority_queue, ** le plus proche du point de départ ** est le prochain sommet à visiter (la partie coût de l'arête est ** la distance du point de départ * N'oubliez pas de mettre à jour vers * puis de plonger dans priority_queue). L'itinéraire le plus court peut être trouvé en répétant une telle mise à jour (nombre de sommets-1) fois. Ici, nous allons considérer la méthode prim en la comparant à la méthode Dyxtra. Dans la méthode Dyxtra, l'exigence finale est la ** distance du point de départ . En d'autres termes, le prochain sommet à visiter sera celui avec la distance la plus courte du point de départ qui n'a pas encore été visité. Par contre, dans la méthode prim, le résultat final est l ' arbre de la superficie totale minimale ** (voir description ci-dessous). En d'autres termes, l'arête suivante à choisir est ** l'arête la moins coûteuse ** qui s'étend du sommet visité au sommet non visité. En raison de ces différences, la méthode Dixtra nécessite que la clé à comparer par priority_queue soit mise à jour à la distance du point de départ, alors que la méthode Prim fait la différence que la clé à comparer par priority_queue est simplement le coût du côté. .. De plus, lors de l'implémentation, si vous mettez votre propre classe dans priority_queue, vous pouvez la faire fonctionner comme prévu en définissant uniquement <. De plus, v1 et v2 sont ici triés par x et y, respectivement. En effet, il est clair que seul le côté qui relie les éléments qui viennent des deux côtés lorsqu'ils sont triés par coordonnées est sélectionné comme côté de l'arborescence de l'aire totale minimale. (Pour plus de détails, voir Explication.)

L'arbre de surface entier est → ** L'arbre qui relie tous les sommets du sous-arbre donné ** Quel est l'arborescence de surface totale minimale? → ** L'arbre de toutes les surfaces minimise le coût total **

answerD.cc

#include<iostream>
#include<queue>
#include<utility>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
typedef long long ll;

class Edge{
public:
  ll to_Node;
  ll cost;
  Edge(ll t,ll c){
    to_Node=t;cost=c;
  }
};

//pr_la file d'attente a une priorité élevée(<Celui qui vient à droite)Est sorti en premier
bool operator< (const Edge& a,const Edge& b){
    return a.cost > b.cost;
};

ll distance(vector<ll>& a,vector<ll>& b){
  return min({abs(a[0]-b[0]),abs(a[1]-b[1])});
}

int main(){
  ll n;cin >> n;
  vector< vector<ll> > v1(n,vector<ll>(3,0));
  vector< vector<ll> > v2(n,vector<ll>(3,0));
  for(ll i=0;i<n;i++){
    ll x,y;cin >> x >> y;
    v1[i][0]=x;v1[i][1]=y;v1[i][2]=i;
    v2[i][0]=x;v2[i][1]=y;v2[i][2]=i;
  }
  sort(v1.begin(),v1.end(),[](vector<ll>&a,vector<ll>&b){returna[0]<b[0];});
  sort(v2.begin(),v2.end(),[](vector<ll>&a,vector<ll>&b){returna[1]<b[1];});

  //Ici, placez le côté s'étendant de chaque nœud dans la file d'attente
  vector< queue<Edge> > edges_before(n);
  for(ll i=0;i<n-1;i++){
    edges_before[v1[i][2]].push(Edge(v1[i+1][2],distance(v1[i],v1[i+1])));
    edges_before[v1[i+1][2]].push(Edge(v1[i][2],distance(v1[i],v1[i+1])));
    edges_before[v2[i][2]].push(Edge(v2[i+1][2],distance(v2[i],v2[i+1])));
    edges_before[v2[i+1][2]].push(Edge(v2[i][2],distance(v2[i],v2[i+1])));
  }

  //Rendez-le visité à partir de 0
  vector<bool> check(n,false);check[0]=true;
  priority_queue<Edge> edges;
  ll l=edges_before[0].size();
  for(ll i=0;i<l;i++){
    edges.push(edges_before[0].front());
    edges_before[0].pop();
  }

  ll cost_sum=0;
  Edge now=edges.top();
  int i=0;
  //Je visiterai de plus en plus dans l'ordre
  while(edges.size()!=0){
    //to_Si le nœud a été visité, si oui, simplement priorité_Retirer simplement de la file d'attente
    if(!check[now.to_Node]){
      check[now.to_Node]=true;//Faites-le visiter
      cost_sum+=now.cost;//Mise à jour du coût total
      int k=now.to_Node;
      ll l=edges_before[k].size();
      edges.pop();//Hors côtés usagés
      for(ll i=0;i<l;i++){//Priorité du côté partant du sommet nouvellement visité_Ajouter à la liste
        Edge s=edges_before[k].front();
        if(!check[s.to_Node]) edges.push(s);//Pousser uniquement les sommets non visités
        edges_before[k].pop();
      }
      now=edges.top();
      //Cela n'a pas été beaucoup plus rapide, mais n fois suffit, alors ↓
      if(++i==n-1)break;
    }else{
      edges.pop();now=edges.top();
    }
  }
  cout << cost_sum << endl;
}