[PYTHON] AtCoder Beginner Contest 126 Review of past questions

This time's results

Impressions of this time

From today, for the time being, I would like to proceed with ABC (6 questions) after 126. Personally, I think the problem has become more sophisticated these days, so be sure to learn it. I would like to attach it. Also, this time I was able to complete it completely. I passed the F problem without much proof, so I would like to review it firmly.

Problem A

I forgot the function to convert to lowercase, so I divided the cases by A, B, or C. Also, the lower function converts to lowercase, which allows you to write pretty code (the second code). Isn't it difficult for A problem?

A.py

n,k=map(int,input().split())
s=input()
if s[k-1]=="A":
    print(s[:k-1]+"a"+s[k:])
elif s[k-1]=="B":
    print(s[:k-1]+"b"+s[k:])
else:
    print(s[:k-1]+"c"+s[k:])

A_shorter.py

n,k=map(int,input().split())
s=input()
print(s[:k-1]+s[k-1].lower()+s[k:])

B problem

The possible month (MM) is 00-12, so keep this as a candidate for the month (cand) and use it as a candidate for the month.

B.py

s=input()
cand={"0"+str(i) if i<10 else str(i) for i in range(1,13)}
if s[:2] in cand and s[2:] in cand:
    print("AMBIGUOUS")
elif s[:2] in cand:
    print("MMYY")
elif s[2:] in cand:
    print("YYMM")
else:
    print("NA")

C problem

I thought about taking the ceil of log, but I avoided it this time because there is an error in the decimal. The only way for Sunuke to win is to show up until ** K or higher ** (because if you put it on the back, it will be 0 and you will lose). Therefore, it is sufficient to count the number of times until it becomes K or more, but since the value of the first dice can be 1 to N, the solution can be found by $ O (N \ log N) $.

C.py

n,k=map(int,input().split())
ans=0
for i in range(1,n+1):
    j,now=0,i
    while now<k:
        j+=1
        now*=2
    ans+=(2**(-j))
print(ans/n)

D problem

Just because it's a tree doesn't mean you should be ready, so you need to be calm. Under the constraints of this problem, there is always ** a way to paint that meets the subject. Now, let's focus on a certain vertex. At this time, it can be said that the vertices connected to the vertices are ** the same color if the length of the side connecting the two vertices is even, and different colors ** if the length is odd. This can be said at any vertex, so if you decide the starting point appropriately and follow it by depth-first search, you can find the solution with $ O (M + N) $.

(The point is to put it into the simple problem of ** what happens at a certain vertex **.)

answerD.py

import sys
sys.setrecursionlimit(10**6)
n=int(input())
path=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    path[u-1].append((v-1,w%2))
    path[v-1].append((u-1,w%2))
ans=[0]+[-1]*(n-1)
def dfs(i):
    global n,path,ans
    for j in path[i]:
        if ans[j[0]]==-1:
            if j[1]:
                ans[j[0]]=1-ans[i]
                dfs(j[0])
            else:
                ans[j[0]]=ans[i]
                dfs(j[0])
dfs(0)
print("\n".join(map(str,ans)))

E problem

It is much easier to solve because it says that there is no contradiction in the given conditions. Also, since there are only two types of each card, I will consider ** full search ** first, but I will reject this policy because it is obviously impossible.

Here, it is only necessary to determine whether $ A_ {x_i} + A_ {y_i} + Z_i $ is an even number. Since $ Z_i $ is known, one of ** $ A_ {x_i} $ and $ A_ {y_i} $ is If you know it, the other one will definitely be decided **. Therefore, it can be seen that the number of each card is ** determined in a chain by the known information $ A_ {x_i} + A_ {y_i} + Z_i $ **, so ** the cards determined in a chain are the same set. You can use Union Find Tree (Disjoint Forest) to manage as **. Of course, you can think of $ A_ {x_i} + A_ {y_i} + Z_i $ as uniting $ A_ {x_i} $ and $ A_ {y_i} $.

Also, since I want to find how many disjoint sets are in the forest, I want to find the member variables after using the grouping function in UnionFind Library. All you have to do is find the size of the group that is.

Implementing this looks like this:

Furthermore, ** the number of disjoint sets in the forest ** is, in general terms, the ** connected component (the largest subgraph in which a path exists between any two vertices). It is equivalent to the number **, and is written in this solution like the latter.

E.cc

//Include(Alphabetical order)
#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<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#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

using namespace std;
typedef long long ll;

//macro
//for loop relationship
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 1.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x is a container such as vector
#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)) //Find the maximum value
#define MIN(x) *min_element(ALL(x)) //Find the minimum value
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair

//Below, the disjoint sets and the tree represent the same thing.
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;//Associative array managed for each disjoint set(key is the parent of each disjoint set, value is an array of elements of that disjoint set)

    //Of the constructor:Initialize member variables after
    UnionFind(ll n):parent(n),siz(n,1){ 
        //Initially initialized as the root of all elements is itself
        for(ll i=0;i<n;i++){parent[i]=i;}
    }

    ll root(ll x){ //Get the root of the tree to which the data x belongs
        if(parent[x]==x) return x;

        return parent[x]=root(parent[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)It is carried out
    }

    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 small set into 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){//Determine if 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){ //Get the size of the disjoint sets of x
        return siz[root(x)];
    }

    //↓ Functions that are not in other people's libraries but are useful
    //O(n)Note that
    void grouping(ll n){//Group disjoint sets
        REP(i,n){
            if(group.find(parent[i])==group.end()){
                group[parent[i]]={i};
            }else{
                group[parent[i]].PB(i);
            }
        }
    }
};

signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin >> n >> m;
    UnionFind uf(n);
    REP(i,m){
        ll x,y,z;cin >> x >> y >> z;
        uf.unite(x-1,y-1);
    }
    REP(i,n)uf.root(i);
    uf.grouping(n);
    cout << SIZE(uf.group) << endl;
}

F problem

I made a convenient pattern and gave an appropriate answer, so Answer and [ARMERIA's blog](https://betrue12. I reviewed it with reference to hateblo.jp/entry/2019/05/20/213302). (However, I think there aren't many people who AC while proving during the contest ...?)

First of all, it was a problem of $ xor $, so I decided to decide one for each bit, but ** I noticed that there were too many patterns and gave up ** (If that is not possible, give up once !!).

So next, I decided to ** focus on two of the same integers **. Here, ** $ xor $ between the same integers becomes $ 0 $ **, so if you arrange them so that they are paired with each other as shown in the figure below, $ xor $ from $ a_i $ to $ a_j $ will change. It is equal to $ xor $ from $ a_ {i + 1} $ to $ a_ {j-1} $, and I thought it would be convenient.

Also, when $ j-i + 1 $ is an even number, all integers can be combined into a set to make the entire $ xor $ $ 0 $, so when $ K $ is $ 0 $, Set $ i = 1, j = 2 ^ {M + 1} $ and build as shown above.

I submitted it because I thought that there was only this pattern, so it became WA, but when I ** switch and continue to consider **, I found that there is also a pattern where $ j-i + 1 $ becomes odd as shown in the figure below. I did.

At this time, by inserting $ K $ in between as shown in the above figure, it is possible to create a set that satisfies the conditions for integers other than $ K $ (since it is sandwiched between them, ** $ K $ is $ 0 $ or more. Must be less than $ 2 ^ M $ **.). This pattern also exists if the XOR of all integers other than $ K $ included in the part between $ K $ is calculated and becomes $ K $.

Furthermore, it was hard to think that it existed other than this highly symmetric pattern (** ← too rough **), so I was able to AC when I set it to -1 except for the above two patterns. Actually, it can be proved that there is no other pattern, so it is shown below.

F.py

from itertools import chain
m,k=map(int,input().split())
if k==0:
    print(" ".join([str(i) for i in chain(range(0,2**m),range(2**m-1,-1,-1))]))
elif 0<k<2**m:
    s=0
    for i in range(0,2**m):
        if i!=k:
            s^=i
    if s==k:
        print(" ".join([str(i) for i in chain(range(0,k),range(k+1,2**m),[k],range(2**m-1,k,-1),range(k-1,-1,-1),[k])]))
    else:
        print(-1)
else:
    print(-1)

F_shortest.py

m,k=map(int,input().split());x=list(range(2**m));print(*x[::-1]+x if k<1 else x[:k:-1]+x[k-1::-1]+[k]+x[:k]+x[k+1:]+[k]if(k<2**m)&(m>1)else[-1])