yukicoder contest 261 Review

result

スクリーンショット 2020-08-15 11.06.22.png

Impressions

I kept bugging with the C problem that I thought was easy, it's painful ... Although I died in a big explosion, I was able to solve the C problem at the last minute, and when I was calm, I could solve four questions, so I will continue my efforts as it is.

Problem A

It won't be that big, so you can do it 100 times.

A.py


def calc(n):
    ret=0
    while n!=0:
        ret+=(n%10)
        n//=10
    return ret
N=int(input())
for i in range(100):
    N=calc(N)
print(N)

Problem B

I thought it would be difficult if $ N $ was even, and when I looked back after the contest, $ N $ was only odd. It's very disappointing to know the odd pattern in about 5 minutes ...

In the case of such a construction, it is difficult to decide on the dark clouds, so ** I think that I decide the rules myself first **. This time, ** decide that the numbers are continuous on each line. Also, when $ N = 5 $, we considered the following two patterns. In the first pattern, the row and diagonal components satisfy the condition, but the column does not satisfy the condition, so the second pattern. Is the correct answer.

(Continuous from left to right)
12345
12345
12345
12345
12345

(Continuous from right to left)
15432
32154
54321
21543
43215

Also, I implemented the above matrix by noting that the last element is +2 each.

B.py


n=int(input())
ans=[]
st=2
if n==1:exit(print(1))
for i in range(n):
    now=[(st+i)%n if st+i!=n else n for i in range(n)][::-1]
    st+=2
    st%=n
    if st==0:st=n
    print(" ".join(map(str,now)))

C problem

It's relatively easy to see what to do, but you need to be careful not to search ** searched multiple times **. In the following, the station is paraphrased as the apex.

First, verify with the following sample at the beginning.

5 4 6
0 2 5 7 8

IMG_0544.PNG

Therefore, considering the subsets connected by edges as described above, in the case of an index included in a certain subset $ X $, the size of $ X $ should be calculated. In addition, ** a collection of disjoint subsets that are not connected by edges can be regarded as a disjoint family **, and can be easily managed by using the ** Union Find tree **.

Here, the vertices to unite in the UnionFind tree are selected in order from the vertex with the smallest coordinates, but since the vertices with a distance of A or more and B or less can be connected, if the coordinates of the currently selected vertex are $ C $, $ CB You can select the vertices that are $ or more and $ CA $ or less or $ C + A $ or more and $ C + B $ or less. Also, ** select the side to connect from the vertices with small coordinates, and since that side is bidirectional, you can select the vertices of $ C + A $ or more and $ C + B $ or less.

In addition, this device alone is not good in terms of calculation amount. This is because the worst complexity of choosing vertices between $ C + A $ and $ C + B $ is $ O (N ^ 2 \ alpha (n)) $. $ \ Alpha (n) $ is the inverse of the Ackermann function $ A (n, n) $ and seems to be smaller than $ \ log {n} $ (this slide See / union-find-49066733)).

Here, in order to consider the searched vertices, if the coordinates of the vertex you are looking at are $ C $ and the coordinates of the vertex you are looking at immediately before are $ C'$, the result will be as shown in the figure below (** Draw a diagram !! **).

IMG_23DFFB46C036-1.jpeg

From the above figure, if you follow the vertices in the direction of decreasing coordinates from the largest vertex below $ C + B $ and connect the edges, and if you hit a vertex in the same disjoint set **, search after that. You can streamline the search by using the method of terminating **. As a result, the search range is not covered, so $ O (N \ alpha (n)) $ can be used to write a high-speed program. In addition, the size of the set included in the disjoint family of sets to be finally obtained can be calculated by $ O (1) $ by the size function.

C.cc


//Debugging options:-fsanitize=undefined,address

//Compiler optimization
#pragma GCC optimize("Ofast")

//Include etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//for loop
//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.
//FORA is a range for statement(If it's hard to use, erase it)
#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--)
#define FORA(i,I) for(const auto& i:I)
//x is a container such as vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array
//Abbreviation
#define PB push_back //Insert
#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,a,b;cin>>n>>a>>b;
    vector<ll> x(n);
    REP(i,n)cin>>x[i];
    UnionFind u(n);
    //Don't check too much
    REP(i,n){
        ll now=upper_bound(ALL(x),x[i]+b)-x.begin();now--;
        //Is it here?
        //From above
        while(now>=0){
            if(x[now]<x[i]+a)break;
            if(u.same(i,now))break;
            u.unite(i,now);
            now--;
        }
    }
    REP(i,n)cout<<u.size(i)<<endl;
}

D problem

It was a simple but interesting problem.

Focusing on how to make a run, if the characters before and after ** are different when a subsequence is selected, the number of runs will increase by one. Therefore, I thought it would be nice to save ** what the last character is ** when scanning the string $ S $ from the front. In addition, there are at most 26 types of characters (** state **) at the end, and it seems that the transition when scanning can be easily defined, so I decided to solve it using DP.

Therefore, we initially defined DP as follows:

$ dp [i] [j]: = $ (number of runs when the last alphabet is $ j $ (= 0 ~ 25) when the $ i $ character is decided)

However, with this definition, addition does not work when considering the transition from $ dp [i-1] $ to $ dp [i] $. If you scrutinize the necessary information here, you can see that the number of character strings ** when deciding up to the ** $ i $ character is necessary for calculating the number of runs. In other words, DP should be defined as follows.

$ dp [i] [j]: = $ (when the last alphabet is $ j $ (= 0 ~ 25) when the $ i $ character is decided (number of character strings, number of runs))

With this definition, transitions can be implemented by dividing the $ i $ character into three cases: (1) selecting the first character of the subsequence, (2) including it in the subsequence, and (3) not including it in the subsequence. I can do it. Also, assume that the alphabet of the $ i $ character is $ d $ and the array of dp is 0-initialized.

(1) When selecting the $ i $ character as the first character in the subsequence dp[i][d][0]+=1 dp[i][d][1]+=1

(2) When the $ i $ character is not included in the subsequence dp[i][j][0]+=dp[i-1][j][0] dp[i][j][1]+=dp[i-1][j][1]

(3) When the $ i $ character is included in the subsequence [1] When $ j = d $ dp[i][d][0]+=dp[i-1][j][0] dp[i][d][1]+=dp[i-1][j][1] [2] When $ j \ neq d $ (run increases by the amount of the character string) dp[i][d][0]+=dp[i-1][j][0] dp[i][d][1]+=(dp[i-1][j][0]+dp[i-1][j][1])

(The problem of subsets is ** the transition is easy to understand if you pay attention to whether you select the element or not **, so it is one of the DPs you want to get used to.)

Also, this will find the sum of the runs of $ dp [n-1] $, but if it is left as it is, it will be MLE. Therefore, since the transition is only $ i-1 \ rightarrow i $, ** saving only these two can reduce the amount of spatial complexity **.

D_MLE.py


s=input()
n=len(s)
#dp[i][j]:=When the i-th letter is decided, it becomes the alphabet j(Number of strings,Number of Runs)
#It's rare to make a pair, but if you don't know either, you can't decide.
#Became MLE
dp=[[[0,0] for i in range(26)] for i in range(n)]
mod=10**9+7
for i in range(n):
    d=ord(s[i])-97
    #Newly added
    dp[i][d]=[1,1]
    if i==0:continue
    #If you do not choose(Will not increase)
    for j in range(26):
        dp[i][j][0]+=dp[i-1][j][0]
        dp[i][j][0]%=mod
        dp[i][j][1]+=dp[i-1][j][1]
        dp[i][j][1]%=mod
    #When choosing(If it is different, it will increase by the number of character strings.)
    for j in range(26):
        if j==d:
            dp[i][j][0]+=dp[i-1][j][0]
            dp[i][j][0]%=mod
            dp[i][j][1]+=dp[i-1][j][1]
            dp[i][j][1]%=mod
        else:
            dp[i][d][0]+=dp[i-1][j][0]
            dp[i][d][0]%=mod
            dp[i][d][1]+=(dp[i-1][j][0]+dp[i-1][j][1])
            dp[i][d][1]%=mod
ans=0
for j in range(26):
    ans+=dp[n-1][j][1]
    ans%=mod
print(ans)

D_AC.py


s=input()
n=len(s)
#dp[i][j]:=When the i-th letter is decided, it becomes the alphabet j(Number of strings,Number of Runs)
#It's rare to make a pair, but if you don't know either, you can't decide.
#Became MLE
#Do not array dp
x,y=[[0,0] for i in range(26)],[[0,0] for i in range(26)]
mod=10**9+7
for i in range(n):
    d=ord(s[i])-97
    #Newly added
    if i==0:
        x[d]=[1,1]
        continue
    #If you do not choose(Will not increase)
    for j in range(26):
        y[j][0]=x[j][0]
        y[j][0]%=mod
        y[j][1]=x[j][1]
        y[j][1]%=mod
    y[d][0]+=1
    y[d][1]+=1
    #When choosing(If it is different, it will increase by the number of character strings.)
    for j in range(26):
        if j==d:
            y[j][0]+=x[j][0]
            y[j][0]%=mod
            y[j][1]+=x[j][1]
            y[j][1]%=mod
        else:
            y[d][0]+=x[j][0]
            y[d][0]%=mod
            y[d][1]+=(x[j][0]+x[j][1])
            y[d][1]%=mod
    x,y=y,x
ans=0
for j in range(26):
    ans+=x[j][1]
    ans%=mod
print(ans)

After the E problem

I will not solve this time.

Recommended Posts

yukicoder contest 259 Review
yukicoder contest 264 Review
yukicoder contest 261 Review
yukicoder contest 267 Review
yukicoder contest 266 Review
yukicoder contest 263 Review
yukicoder contest 268 Review
AtCoder Beginner Contest 152 Review
AtCoder Grand Contest 041 Review
yukicoder contest 265 Participation record
AtCoder Regular Contest 105 Review
yukicoder contest 266 Participation record
yukicoder contest 243 Participation record
yukicoder contest 256 entry record
yukicoder contest 273 Participation record
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 167 Review
yukicoder contest 252 Participation record
yukicoder contest 259 Participation record
AtCoder Beginner Contest 164 Review
yukicoder contest 249 Participation record
AtCoder Beginner Contest 169 Review
yukicoder contest 271 Participation record
AtCoder Grand Contest 048 Review
yukicoder contest 267 entry record
AtCoder Beginner Contest 181 Review
yukicoder contest 251 Participation record
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
yukicoder contest 242 Participation record
AtCoder Beginner Contest 180 Review
yukicoder contest 241 Participation record
yukicoder contest 277 Participation record
AtCoder Beginner Contest 177 Review
yukicoder contest 264 entry record
AtCoder Beginner Contest 168 Review
AtCoder Grand Contest 045 Review
NOMURA Programming Contest 2020 Review
AtCoder Grand Contest 044 Review
yukicoder contest 245 entry record
yukicoder contest 257 Participation record
yukicoder contest 250 entry record
yukicoder contest 254 Participation record
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Regular Contest 106 Review
yukicoder contest 246 Participation record
yukicoder contest 275 Participation record
yukicoder contest 274 Participation record
AtCoder Beginner Contest 176 Review
yukicoder contest 247 Participation record
AtCoder Grand Contest 046 Review
AtCoder Beginner Contest 175 Review
HHKB Programming Contest 2020 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
yukicoder contest 261 Participation record
AtCoder Beginner Contest 170 Review