AtCoder Beginner Contest 126 Review of past questions

This time's results

スクリーンショット 2020-06-05 0.45.33.png

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.

IMG_0398.JPG

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.

IMG_0400.JPG

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.

Proof

Up to the above, we have shown that there is a sequence that satisfies the condition when $ k = 0 $ ((1)) (the pattern in the first figure).

Here, "When $ 0 \ leqq K <2 ^ M $, $ xor $ obtained by subtracting $ K $ from the number of $ 0 $ or more and less than $ 2 ^ M $ becomes $ K $. "Exists" (②) is shown first (the pattern in the second figure), and then it is shown that there is no sequence that satisfies the condition when $ k \ geqq 2 ^ M $ (③).


Here, using that ** $ xor $ of two consecutive integers $ 2a, 2a + 1 $ ($ a $ is an integer) becomes 1, ** the whole number of $ 0 $ or more and less than $ 2 ^ M $ For $ xor $ of $ M \ geqq 2 $, you can make an even number of pairs of two consecutive integers $ 2a, 2a + 1 $ ($ a $ is an integer) **. Therefore, the total $ xor $ is $ 0 $ because there are an even number of pairs where $ xor $ is $ 1 $ (the addition theorem of $ \ because $$ xor $).

Also, when the total $ xor $ of the number of $ 0 $ or more and less than $ 2 ^ M $ is $ 0 $, $ xor $ excluding $ K $ becomes $ K $ **, so (\ because $) It is shown that the above pattern holds for K \ xor \ K = 0 $) and $ M \ geqq 2 $.

Also, when $ M = 0 $ and $ M = 1 $, the number ** of $ 0 $ or more and less than $ 2 ^ M $ is not $ 0 $, so $ xor $ excluding $ K $ is It does not become $ K $, and even if you write out possible cases, you cannot create a sequence that meets the conditions.

Therefore, ② was shown.


Furthermore, in the case of $ k \ geqq 2 ^ m $, there are some bits that are $ M $ or higher and become 1, but the number of $ 0 $ or more and less than $ 2 ^ M $ is $ M $ or higher. There is nothing that can be 1, so it doesn't exist either. Therefore, ③ was shown.

From (1), (2), and (3) above, you can show that your solution is necessary and sufficient.

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])

Recommended Posts

AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 085 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 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 054 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 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 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 047 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 103 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 124 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