AtCoder Beginner Contest 097 Review of past questions

Time required

スクリーンショット 2020-04-06 10.31.45.png

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.

IMG_0181.JPG

(✳︎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;
}

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 113 Review of past questions
AtCoder Beginner Contest 074 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 105 Review of past questions
AtCoder Beginner Contest 112 Review of past questions
AtCoder Beginner Contest 076 Review of past questions
AtCoder Beginner Contest 089 Review of past questions
AtCoder Beginner Contest 069 Review of past questions
AtCoder Beginner Contest 079 Review of past questions
AtCoder Beginner Contest 056 Review of past questions
AtCoder Beginner Contest 087 Review of past questions
AtCoder Beginner Contest 067 Review of past questions
AtCoder Beginner Contest 093 Review of past questions
AtCoder Beginner Contest 046 Review of past questions
AtCoder Beginner Contest 123 Review of past questions
AtCoder Beginner Contest 049 Review of past questions
AtCoder Beginner Contest 078 Review of past questions
AtCoder Beginner Contest 081 Review of past questions
AtCoder Beginner Contest 047 Review of past questions
AtCoder Beginner Contest 060 Review of past questions
AtCoder Beginner Contest 104 Review of past questions
AtCoder Beginner Contest 057 Review of past questions
AtCoder Beginner Contest 121 Review of past questions
AtCoder Beginner Contest 126 Review of past questions
AtCoder Beginner Contest 090 Review of past questions
AtCoder Beginner Contest 061 Review of past questions
AtCoder Beginner Contest 059 Review of past questions
AtCoder Beginner Contest 044 Review of past questions
AtCoder Beginner Contest 083 Review of past questions
AtCoder Beginner Contest 048 Review of past questions
AtCoder Beginner Contest 116 Review of past questions
AtCoder Beginner Contest 097 Review of past questions
AtCoder Beginner Contest 088 Review of past questions
AtCoder Beginner Contest 092 Review of past questions
AtCoder Beginner Contest 099 Review of past questions
AtCoder Beginner Contest 065 Review of past questions
AtCoder Beginner Contest 053 Review of past questions
AtCoder Beginner Contest 094 Review of past questions
AtCoder Beginner Contest 063 Review of past questions
AtCoder Beginner Contest 107 Review of past questions
AtCoder Beginner Contest 071 Review of past questions
AtCoder Beginner Contest 064 Review of past questions
AtCoder Beginner Contest 082 Review of past questions
AtCoder Beginner Contest 084 Review of past questions
AtCoder Beginner Contest 068 Review of past questions
AtCoder Beginner Contest 058 Review of past questions
AtCoder Beginner Contest 043 Review of past questions
AtCoder Beginner Contest 098 Review of past questions
AtCoder Beginner Contest 114 Review of past questions
AtCoder Beginner Contest 045 Review of past questions
AtCoder Beginner Contest 120 Review of past questions
AtCoder Beginner Contest 108 Review of past questions
AtCoder Beginner Contest 106 Review of past questions
AtCoder Beginner Contest 122 Review of past questions