Codeforces Round # 606 (Div. 3) Bacha Review (10/13)
This time's results
Impressions of this time
This time, I had to solve the problem up to E, but I couldn't solve it because I lost my concentration. ** If you paraphrase one by one, you should be able to solve the E problem **, but I am very disappointed because I could not solve it within the contest.
Problem A
Since it is a positive number that repeats the same number, consider how many ways there are in the nine cases of $ 11… 11,22… 22,…, 99… 99 $. Here, even if $ n = 10 ^ 9 $, there are only 9 ways for each, so you can count the ones under $ n $.
A.py
for _ in range(int(input())):
n=int(input())
ans=0
for i in range(1,10):
cand=[]
while True:
cand.append(str(i))
x=int("".join(cand))
if x<=n:
ans+=1
else:
break
print(ans)
Problem B
All even and equal elements are divided by 2, so if you keep only the ** element type, you can get the number of simulations. Therefore, prepare $ a $ as a $ set $ structure that holds the elements (even numbers) that need to be manipulated.
When working on the elements inside $ a $, each operation only reduces the number of each. Therefore, if you perform the operation ** that divides by 2 in order from the largest number included in ** $ a $, this will be the minimum number of operations. Also, if the result of dividing by 2 is odd, it is not necessary to reinsert it in $ a $. Therefore, the minimum number of operations in the subject is the number of operations until $ a $ becomes empty after performing these operations in order.
B.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
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(i,t){
ll n;cin>>n;
set<ll> a;
REP(j,n){
ll x;cin>>x;
if(x%2==0)a.insert(x);
}
ll ans=0;
//cout<<SIZE(a)<<endl;
while(SIZE(a)>0){
ll y=*--a.end();a.erase(y);
y/=2;
if(y%2==0)a.insert(y);
ans++;
//cout<<SIZE(a)<<endl;
}
cout<<ans<<endl;
}
}
C problem
Consider a string that does not include one and two except for a few characters. Here, if ** one and two exist without overlapping **, you can remove the middle n and w respectively so that the character string after pulling out does not include that one and two. I will. At this time, one and two are ** nothing new **.
The trouble is when ** one and two overlap and become two **. At this time, by removing o, the character string twone becomes twne, and neither one nor two included in this character string is included in the character string after it is removed. Also, there is nothing new that one and two can do as before.
In addition, what should be output is the number of times to exclude and the index of the characters to be excluded. Here, ** the index deviates from the initial state when the character is actually pulled out **, so check it as the character to be pulled out instead of pulling it out. Also, in order to ** avoid duplicating counting ** in the case of two and one, scan the ones that become two first and check in advance, and then count the ones that become two, one. Did.
C.py
import sys
input=sys.stdin.readline
for _ in range(int(input())):
s=input()
n=len(s)
check=[0]*n
ans=[]
for i in range(n):
if s[i:i+5]=="twone":
ans.append(str(i+3))
for j in range(i,i+5):
check[j]=1
for i in range(n):
if check[i]:
continue
if s[i:i+3]=="one":
ans.append(str(i+2))
if s[i:i+3]=="two":
ans.append(str(i+2))
print(s.count("one")+s.count("two")-s.count("twone"))
print(" ".join(ans))
D problem
Despite the ** consideration and implementation being different **, I was impatient because there was a sample for some reason because I made a mistake in two places. It's good to be able to find bugs after that, but I want to reduce such mistakes so that I don't get impatient.
Simply put, it's a matter of shiritori between binary strings. Also, consider the case where the character strings may be inverted so that they do not match, and the number of inversions is as small as possible while shiritori is possible. Since it is useless to perform the reverse operation on the same character string more than once here, consider that the reverse operation is performed at most once for each character string.
Also, since only the reverse operation can be performed, the characters in between are considered as a pattern of ** $ 00,01,10,11 $ regardless of whether or not they can be shiritori **. Here, for $ 00,11 $, the reversal operation does not affect the shiritori, so the reversal operation ** is performed only between ** $ 01 $ and $ 10 $. Also, if only one of $ 00 and 11 $ is included here, the shiritori cannot be self-explanatory, so -1 is output.
Here, suppose that $ 01 $ is $ a $ and $ 10 $ is $ b $, and $ a > b $ (the same is true for $ a \ <b $, and $ a = b $ is self-evident. It holds). Here, considering the conditions under which shiritori can be taken, it is when $ 01 → 10 → 01 →… $ or $ 10 → 01 → 01 →… $ are lined up, and it should be ** $ ab \ leqq 1 $ ** is. To achieve this, you only need to invert $ [\ frac {a-b} {2}] $ out of ** $ 01 $ **, but you cannot select strings that are the same when inverted. Also, the number of character strings that match between the $ 01 $ pattern and the $ 10 $ pattern by the inversion operation is $ l
Therefore, it is possible to judge whether it will be possible to invert and shiritori, and at that time, the number of elements that require inversion operation can be obtained, so you can select from $ 01 $ for the number of elements. At this time, please note that only those that do not match what is included in ** $ 10 $ are selected **.
D.py
for _ in range(int(input())):
n=int(input())
s=[input() for i in range(n)]
t=set(s)
a,b,c,d=set(),set(),set(),set()
for i in range(n):
if s[i][0]=="0":
if s[i][-1]=="0":
c.add(i)
else:
a.add(i)
else:
if s[i][-1]=="0":
b.add(i)
else:
d.add(i)
l=set()
for i in range(n):
if (i in a or i in b) and (s[i][::-1] in t):
l.add(i)
la,lb,lc,ld,ll=len(a),len(b),len(c),len(d),len(l)
#print(la,lb,lc,ld,ll)
if la==0 and lb==0:
if lc==0 or ld==0:
print(0)
else:
print(-1)
continue
if lb>la:
if lb-ll//2<(lb-la)//2*2:
print(-1)
continue
x=(lb-la)//2
print(x)
if x==0:
continue
ans=[]
for i in b:
if i not in l:
ans.append(str(i+1))
x-=1
if x==0:
break
print(" ".join(ans))
elif la>lb:
if la-ll//2<(la-lb)//2*2:
print(-1)
continue
x=(la-lb)//2
print(x)
if x==0:
continue
ans=[]
for i in a:
if i not in l:
ans.append(str(i+1))
x-=1
if x==0:
break
print(" ".join(ans))
else:
print(0)
E problem
I'm very disappointed because it seemed to be solved soon. I upsolved by referring to Hamayanhamayan's article.
Such a problem ** tends to explode the amount of calculation if it is done with an image of searching from each vertex **, so it is a typical pattern to paraphrase using the characteristics of the graph.
Here, in other words, you must pass through both $ A and B $, in other words, if you can reach without passing through either $ A or B $, or if you can reach using only either $ A or B $ * * Excluded ** in case (** Consider denial of condition! **). In the former case, the vertices in the connected component when all the edges connected to ** $ A and B $ are deleted **, so to exclude the former case, ** vertices contained in different connected components ** Just think about it.
In the latter case, it didn't work because I thought about the connected component when I used the side connected only to $ A $ (or $ B $), but ** I will consider using the connected component earlier ** Is good (** Consistency of consideration! **). Here, the graph when all the edges connected to $ A and B $ are deleted is unconnected, but each connected component is directly connected to either ** $ A or B $ by its definition **. Take advantage of that. At this time, each connected component has only three patterns: connected to either $ A or B $ (①), connected only to $ A $ (②), and connected only to $ B $ (③). There is none. Of these, only patterns (2) and (3) always pass through $ A and B $ for any of the paths connecting the two points (you can easily find out by trying all six ways).
Therefore, (the number of vertices included in the connected component of the pattern ②) $ \ times $ (the number of vertices included in the connected component of the pattern ③) outputs this as the answer.
E.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,set<ll>> group; //Manage by set(key:Set representative element, value:Array of elements of the set)
ll n; //Element count
//constructor
UnionFind(ll n_):n(n_),parent(n_),siz(n_,1){
//Initialize as the root of all elements is itself
for(ll i=0;i<n;i++){parent[i]=i;}
}
//Get the root of the tree to which the data x belongs(Also performs path compression)
ll root(ll x){
if(parent[x]==x) return x;
return parent[x]=root(parent[x]);//Since the value of the assignment expression is the value of the assigned variable, the route can be compressed.
}
//Merge x and y trees
void unite(ll x,ll y){
ll rx=root(x);//root of x
ll ry=root(y);//root of y
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
}
//Determine if the tree to which x and y belong is the same
bool same(ll x,ll y){
ll rx=root(x);
ll ry=root(y);
return rx==ry;
}
//Get the size of the disjoint sets of x
ll size(ll x){
return siz[root(x)];
}
//Group each disjoint set
void grouping(){
//Perform route compression first
REP(i,n)root(i);
//Manage with map(Use default build)
REP(i,n)group[parent[i]].insert(i);
}
//Delete the disjoint sets and initialize
void clear(){
REP(i,n){parent[i]=i;}
siz=vector<ll>(n,1);
group.clear();
}
};
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll t;cin>>t;
REP(_,t){
ll n,m,a,b;cin>>n>>m>>a>>b;a--;b--;
UnionFind uf(n);
set<ll> otheredgesA,otheredgesB;
REP(i,m){
ll u,v;cin>>u>>v;u--;v--;
if(u!=a and u!=b and v!=a and v!=b){
uf.unite(u,v);
}
if(u==a){
otheredgesA.insert(v);
}
if(v==a){
otheredgesA.insert(u);
}
if(u==b){
otheredgesB.insert(v);
}
if(v==b){
otheredgesB.insert(u);
}
}
uf.grouping();
ll countA=0;ll countB=0;
FORA(i,uf.group){
bool checkA=false;bool checkB=false;
if(i.F==a or i.F==b)continue;
FORA(j,i.S){
if(otheredgesA.find(j)!=otheredgesA.end()){
checkA=true;
}
if(otheredgesB.find(j)!=otheredgesB.end()){
checkB=true;
}
}
if(!checkB){
countA+=SIZE(i.S);
}
if(!checkA){
countB+=SIZE(i.S);
}
}
cout<<countA*countB<<endl;
}
}
F problem
I will skip this time.
Recommended Posts