[PYTHON] AtCoder Beginner Contest 070 Review of past questions

The second past question that I have solved before

Time required

Problem A

Just judge whether the beginning and the end are the same (handle as a character string as it is)

answerA.py

n=input()
if n[0]==n[-1]:
    print("Yes")
else:
    print("No")

B problem

Since the common part (the time that two people are pushing) is between max of a and c and min of b and d, if it exists, it is sufficient to find the time. ..

answerB.py

a,b,c,d=map(int,input().split())
k,l=max(a,c),min(b,d)

if k>=l:
    print(0)
else:
    print(l-k)

C problem

The least common multiple problem that can be understood in 2 seconds, I solved it in Python the last time I solved it, but this time I solved it in C ++. Python just needs to use the gcd function to get lcm, but C ++ doesn't. (For the time being, both gcd and lcm are implemented in C ++ and made into a library) First, you have to use a long long because it doesn't fit in an int due to the constraints of the problem (long long is always ll). Furthermore, at lcm, there was a multiplication ** that could exceed the range of ** long long, so ** the division was done first, and then the multiplication was done **.

answerC.cc

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

//Make it smaller with while
ll gcd(ll x,ll y){
  if(x<y) swap(x,y);
  //x is always larger
  while(y>0){
    ll r=x%y;
    x=y;
    y=r;
  }
  return x;
}

ll lcm(ll x,ll y){
  //It gets too big when you put it on
  return ll(x/gcd(x,y))*y;
  //Originally ll(x*y/gcd(x,y));Was doing
}

int main(){
  ll n;cin >> n;
  ll ans=1;
  for(int i=0;i<n;i++){
    //cout << ans << endl;
    ll t;cin >> t;
    ans=lcm(ans,t);
  }
  cout << ans << endl;
}

answerC.py

import fractions
n=int(input())
t=[int(input()) for i in range(n)]

if n==1:
    print(t[0])
else:
    x=t[0]*t[1]//fractions.gcd(t[0],t[1])
    for i in range(1,n-1):
        x=x*t[i+1]//fractions.gcd(x,t[i+1])
    print(x)

D problem

I have decided to do the tree structure in C ++ (because it is difficult to estimate the amount of calculation and it is often difficult to do it in Python). The first code is the code you solved before, and the second code is the code you solved this time. When I solved it the first time, I took too much time thinking about devising it, but in the end it is clear that I want to know the distance, so considering that it is a tree, I can usually do a depth-first search or breadth-first search. I understand. (** I always think that the abstraction of the search problem in the tree structure often fails. ) Here, I chose depth-first search (for no reason), tree that holds the information of the edge extending from each Node, tree_len that holds the shortest path from k, and check that holds whether or not a visit was made. If prepared, the shortest path from k can be obtained by performing a normal depth-first search. Once asked, the answer is to add the length of the shortest path in k → x and the length of the shortest path in k → y in each question query. ( I want to be able to write the code of depth-first search quickly without making it into a library. The point is to thoroughly rewrite the information of the current Node and when calling the Node connected from it recursively. Don't forget to write the code to check if you have visited. **) Also, this problem also overflows with ** int, so it is necessary to make it long long **. In addition, I made a mistake ** because it is a tree, so I thought it was n even though it had only n-1 edges, and tried to receive input, and it went into an input standby state **.

answerD.cc

#include<iostream>
#include<vector>
#include<utility>
using namespace std;

class Node{
public:
  vector< pair<int,int> > v;
  long long dist;
  bool check=false;
};

void depth_search(vector<Node>& V,int k,long long d){
  V[k].dist=d;
  V[k].check=true;
  int l=V[k].v.size();
  for(int i=0;i<l;i++){
    if(V[V[k].v[i].first].check==false){
      depth_search(V,V[k].v[i].first,V[k].v[i].second+d);
    }
  }
}

int main(){
  int n;cin >> n;
  vector<Node> V(n);
  for(int i=0;i<n-1;i++){
    int a,b,c;cin >> a >> b >> c;
    V[a-1].v.push_back(make_pair(b-1,c));
    V[b-1].v.push_back(make_pair(a-1,c));
  }
  int q,k;cin >> q >> k;k-=1;
  depth_search(V,k,0);
  vector<long long> Q(q);
  int x,y;
  for(int i=0;i<q;i++){
    cin >> x >> y;
    Q[i]=V[x-1].dist+V[y-1].dist;
  }
  for(int i=0;i<q;i++){
    cout << Q[i] << endl;
  }
}

answerD.cc

#include<iostream>
#include<vector>
#include<utility>
using namespace std;
typedef long long ll;
typedef vector< vector< pair<long long,long long> > > vvp;

//It's smarter not to create a Node class, so that you can write this faster
void dfs(vvp& tree,vector<ll>& tree_len,vector<bool>& check,ll dep,ll now){
  tree_len[now]=dep;
  check[now]=true;
  ll l=tree[now].size();
  for(int i=0;i<l;i++){
    if(check[tree[now][i].first]==false) dfs(tree,tree_len,check,dep+tree[now][i].second,tree[now][i].first);
  }
}

int main(){
  ll n;cin >> n;
  vvp tree(n);//Information on the side extending from Node
  vector<ll> tree_len(n,0);//Shortest path retention
  vector<bool> check(n,false);//Whether you followed
  //I couldn't finish typing with n
  for(int i=0;i<n-1;i++){
    ll a,b,c;cin >> a >> b >> c;
    tree[a-1].push_back(make_pair(b-1,c));
    tree[b-1].push_back(make_pair(a-1,c));
  }
  ll q,k;cin >> q >> k;
  dfs(tree,tree_len,check,0,k-1);
  for(int i=0;i<q;i++){
    ll x,y;cin >> x >> y;
    cout << tree_len[x-1]+tree_len[y-1] << endl;
  }
}