[PYTHON] AtCoder Beginner Contest 065 Review of past questions

Past questions solved for the first time

Time required

Problem A

answerA.py

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

With the ternary operator

answerA_better.py

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

B problem

Connect the glowing ones in order. I was filling AtCoder with B at the very beginning, and I felt growth when I saw that it was not done well at that time.

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)

C problem

I made a table of binomial coefficients, but I didn't need it.

answerC.cc

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

const int MAX = 10000000;
//What to divide by
const int MOD = 1000000007;

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

//Pretreatment to make a 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;
    }
}

//Binomial coefficient calculation
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(){
  //Preprocessing
  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;
  }
}

D problem

When I first saw it, I didn't really know what to do (because the method I thought was likely to be TLE). Looking at the answer, it seems that the minimum spanning tree is used, so when I investigated it, I found that there are two methods, Prim's method and Kruskal's method. The latter says to use UnionFind, and UnionFind is not very familiar (I forgot to implement it because I used it too much, I have to advance the spiral book quickly), so when I try to implement it with Prim's algorithm, a lot of bugs occur. I've melted a good amount of time. (** Priority_queue implementation bugs tend to make you forget that pushing can change the top **) Prim's algorithm is an algorithm that is quite similar to Dijkstra's algorithm. In Dijkstra's algorithm, the starting point is determined and the nearest vertex that can be reached from that starting point is set as the next vertex to be visited, and after that, the vertices included in the visited vertex set are visited in order from the closest vertex. I will. In other words, prepare an array with information on (multiple) Edges extending from each vertex, extract only the Edges extending from the visited vertices, and plunge them into the priority_queue. Then, of the vertices that have not yet been visited, which can be reached through the Edge that plunges into the priority_queue, the ** closest to the start point ** is the next vertex to be visited (the cost part of the Edge is ** the distance from the start point *. Don't forget to update to * and then plunge into priority_queue). The shortest path can be found by repeating such an update (number of vertices-1) times. Here, we will consider the Prim's algorithm while comparing it with the Dijkstra's algorithm. In Dijkstra's algorithm, what we finally want to find is the ** distance from the starting point **. In other words, the next vertex to visit will be the vertex that is the shortest distance from the starting point and has not yet been visited. In contrast, in Prim's algorithm, the final result is the ** minimum spanning tree ** (see description below). In other words, the next edge to choose is ** the edge with the lowest cost that extends from the visited vertices to the unvisited vertices **. Due to these differences, the Dijkstra method requires the key to be compared by priority_queue to be updated to the distance from the starting point, whereas the Prim's method makes the difference that the key to be compared by priority_queue is simply the cost of the edge. .. Also, when implementing, if you put your own class in priority_queue, you can make it work as expected by defining only <. Furthermore, v1 and v2 here are sorted by x and y, respectively. This is because it is clear that only the edges connecting the adjacent objects when sorted by coordinates are selected as the edges of the minimum spanning tree. (For details, see Explanation.)

A spanning tree is a tree that connects all the vertices of a given subtree ** What is the minimum spanning tree? → ** Spanning tree that minimizes the total cost **

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_queue has high priority(<The one who comes to the right)Is taken out first
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];});

  //Here, put the side extending from each Node in the queue
  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])));
  }

  //Make it visited starting from 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;
  //I will visit more and more in order
  while(edges.size()!=0){
    //to_Whether Node has been visited, if visited, simply priority_Simply remove from queue
    if(!check[now.to_Node]){
      check[now.to_Node]=true;//Make it visited
      cost_sum+=now.cost;//Total cost update
      int k=now.to_Node;
      ll l=edges_before[k].size();
      edges.pop();//Excluding used sides
      for(ll i=0;i<l;i++){//Priority of the side extending from the newly visited apex_Add to queue
        Edge s=edges_before[k].front();
        if(!check[s.to_Node]) edges.push(s);//Push only unvisited vertices
        edges_before[k].pop();
      }
      now=edges.top();
      //It didn't get much faster, but n times is enough, so ↓
      if(++i==n-1)break;
    }else{
      edges.pop();now=edges.top();
    }
  }
  cout << cost_sum << endl;
}