[PYTHON] AtCoder Beginner Contest 097 Review of past questions

Time required

Impressions

I couldn't solve it during the contest because other errands entered during the contest. Also, I have a lot of ABC reviews, so I will not do a new virtual console today tomorrow. The FX I'm doing now hasn't been cut off, so I'd like to organize that area well.

Problem A

You just have to decide whether you can talk directly or indirectly.

answerA.py

a,b,c,d=map(int,input().split())
print("Yes" if abs(a-c)<=d or (abs(a-b)<=d and abs(b-c)<=d) else "No")

B problem

Such problems related to exponentiation and division have issued WA multiple times even though errors are likely to occur. For such problems, I want to be careful to separate cases at the boundary and avoid using functions such as ceil, floor, and log.

answerB.py

x=int(input())
ans=[1]
for i in range(2,x+1):
    k=2
    while True:
        a=i**k
        if a<=x:
            ans.append(a)
            k+=1
        else:
            break
print(max(ans))

C problem

The K-th smallest one is calculated in the dictionary order, but the dictionary order is calculated by ** alphabetical order ** and ** length **. At first, I wrote the code focusing on the ** alphabetical order ** and TLE it, but when I added the ** length ** constraint to it, I was able to AC.

answerC.py

s=input()
l=len(s)
k=int(input())
alp=[chr(i) for i in range(97, 97+26)]
ans=set()
for i in range(26):
    for j in range(l):
        if s[j]==alp[i]:
            for m in range(j,min(l,j+k)):
                ans.add(s[j:m+1])
    if len(ans)>=k:
        break
print(sorted(list(ans))[k-1])

D problem

I couldn't solve it because I had something to do during the virtual console, but it wasn't that difficult. ** There was a feeling that elements that can be replaced (may go through multiple replacements) can be replaced without replacing other elements **, so I passed it without proof ( ✳︎ 1). ** I think it's hard to do uncertified things on a regular basis **, so I regret it. Assuming this is correct, we will create a Union-Find tree ** with a set containing replaceable elements as a disjoint set, and then use the grouping function to separate each set. If the processing up to this point can be performed, the rest should be considered when $ p_i = i $ holds as much as possible for the elements contained in each disjoint set. Here, since the disjoint set contains the index value, it can be obtained by ** taking the product set (intersection) of the disjoint set and the set of elements of p whose index is that element **. .. You can find the maximum value of i such that $ p_i = i $ by setting_intersection with the set you want to find as an argument and finding the total length of the intersection for each disjoint set. (✳︎2)

(✳︎1)… The mathematical proof is written in Answer, so I will skip it, but the sensory proof is as follows. I will.

(✳︎2)… For how to use set_intersection, I referred to this blog.

answerD.cc

//Reference: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Include
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
#include<iterator>//set_intersection,set_union,set_Because of difference

using namespace std;
typedef long long ll;

//macro
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define MAXR 100000 //10^5:Maximum range(Used for prime number enumeration etc.)

//Reference: https://pyteyon.hatenablog.com/entry/2019/03/11/200000
//Reference: https://qiita.com/ofutonfuton/items/c17dfd33fc542c222396

class UnionFind {
public:
    vector<ll> parent; //parent[i]Is the parent of i
    vector<ll> siz; //An array representing the size of the disjoint sets(Initialize with 1)
    map<ll,vector<ll>> group;

    //Of the constructor:Behind is initializing member variables
    UnionFind(ll n):parent(n),siz(n,1){ //Initialize as everything is root at first
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    ll root(ll x){ //Recursively get the root of the tree to which the data x belongs
        if(parent[x]==x) return x;
        //The value of the assignment expression will be the value of the assigned variable!
        //Path compression(Streamline calculations by connecting elements directly to the roots)
        return parent[x]=root(parent[x]);
        //Update the parent when recursion
    }

    void unite(ll x,ll y){ //Merge x and y trees
        ll rx=root(x);//The root of x is rx
        ll ry=root(y);//y root ry
        if(rx==ry) return; //When in the same tree
        //Merge a small set into a large set(Merged from ry to rx)
        if(siz[rx]<siz[ry]) swap(rx,ry);
        siz[rx]+=siz[ry];
        parent[ry]=rx; //If x and y are not in the same tree, add y root ry to x root rx
    }

    bool same(ll x,ll y){//Returns whether the tree to which x and y belong is the same
        ll rx=root(x);
        ll ry=root(y);
        return rx==ry;
    }

    ll size(ll x){ //Disjoint size
        return siz[root(x)];
    }

    void grouping(ll n){ //Grouping of disjoint sets
        for(ll i=0;i<n;i++){
            if(group.find(parent[i])==group.end()){
                group[parent[i]]=vector<ll>(1,i);
            }else{
                group[parent[i]].push_back(i);
            }
        }
    }
};


signed main(){
    ll n,m;cin >> n >> m;
    UnionFind uf(n);
    vector<ll> p(n);REP(i,n){cin >> p[i];p[i]-=1;}
    REP(i,m){
        ll x,y;cin>>x>>y;
        uf.unite(x-1,y-1);
    }
    REP(i,n)uf.root(i);
    uf.grouping(n);
    ll ans=0;
    for(auto j=uf.group.begin();j!=uf.group.end();j++){
        vector<ll> value=j->S;
        //REP(i,value.size()) cout << value[i] << " ";
        vector<ll> vecinter;
        vector<ll> value2;REP(i,value.size()) value2.PB(p[value[i]]);
        sort(ALL(value));sort(ALL(value2));
        //Don't forget to sort
        set_intersection(ALL(value),ALL(value2),back_inserter(vecinter));
        //cout << ans << endl;
        ans+=vecinter.size();
        //cout << endl;
    }
    cout << ans << endl;
}