yukicoder contest 261 Review
result
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
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 !! **).
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
(2) When the $ i $ character is not included in the subsequence
(3) When the $ i $ character is included in the subsequence
[1] When $ j = d $
(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