[PYTHON] Codeforces Round # 603 (Div. 2) Bacha Review (10/15)
This time's results
Impressions of this time
I was able to solve up to D, but E felt that he was still out of reach. The idea was that the E problem came out, but the implementation exploded. I think it was good that I was able to solve D in this time (although C took a long time to mystery). Also, this issue was very difficult to read, so I resent Writer.
Problem A
It seemed intuitive to solve, but it was difficult to solve. In the following, we will proceed with the discussion as $ r \ <g \ <b $.
At first, I took the policy of selecting a lot of $ g and b $ and combining the rest with $ r $, but it was a wonderful lie solution without even passing a sample. From the idea of ** combining from the most, ** (TLE if it is foolish), I came up with the following solution (unproven, but probably correct).
① Combine $ g and b $ until $ g = r $ At this time, only $ m = g-r $ can be paired. The $ g and b $ used for the pair will be updated.
② Consider the combination under $ r = g \ <b $
(1) When $ r + g \ leqq b $ At this time, both $ r and g $ can be combined with $ b $, so $ m + r + g $ is output.
(2) When $ r + g> b $ $ r, g $ are staggered with $ b $. That is, both $ r and g $ can be combined with $ b $ by $ [\ frac {b} {2}] $. Also, since the remaining $ r and g $ are the same number, you can combine $ r and g $ together. Therefore, you can output $ m + [\ frac {b} {2}] \ times 2 + r (= m + [\ frac {b} {2}] \ times 2 + g) $ ($ in this formula). r, g $ is the rest).
A.py
for _ in range(int(input())):
r,g,b=sorted(list(map(int,input().split())))
m=g-r
g-=m
b-=m
#print(r,g,b)
if r+g<=b:
print(m+r+g)
else:
n=b
r-=n//2
g-=n//2
print(m+n//2*2+r)
Problem B
Since ** $ n $ is at most 10 **, you can make everything different by changing only one digit. Therefore, the minimum number of times to change is (the number of the same PIN) -1, and you can save it in the dictionary as (PIN, number) and count it. Also, ** generate a PIN so that the newly created one does not match the original one, but you can use the dictionary above and change it the minimum number of times so that only the first digit is not covered. .. The idea itself is simple, so I will do my best by ** devising the implementation **.
B.py
for _ in range(int(input())):
n=int(input())
d=dict()
c=[]
for i in range(n):
x=input()
if x in d:
d[x]+=1
else:
d[x]=1
c.append(x)
ans=0
for i in d:
ans+=(d[i]-1)
ansa=[]
for i in range(n):
if d[c[i]]==1:
ansa.append(c[i])
continue
for j in range(10):
x=f"{j}"+c[i][1:]
if x not in d:
d[c[i]]-=1
d[x]=1
ansa.append(x)
break
print(ans)
for i in range(n):
print(ansa[i])
C problem
I'm addicted to it for some reason. You should like this kind of problem ...
Since $ n $ is fixed at $ [\ frac {n} {k}] $, we will experiment to see the behavior by moving ** $ k $ **. Here, $ n $ given in the sample is small and the behavior cannot be grasped, so if you think about $ n = 100 $, it will be as follows. Also, [] is omitted.
Then you can see that the answers are continuous at $ k \ geqq 8 $. Therefore, ** it is assumed that everything is continuous up to 0 after the number of consecutive numbers **, all are listed until the continuous ones appear, and after that, they are listed in order up to 0 and sorted in ascending order is output. I decided to. Also, although I did not prove it, consider the graph of ** $ f (k) = \ frac {n} {k} $ ** and the slope becomes smaller as $ k $ increases, and $ k $ becomes It is self-evident as it gradually approaches 0 as it grows larger.
C.py
for _ in range(int(input())):
n=int(input())
ans=[]
i=1
while i<n:
if len(ans)!=0:
if ans[-1]==n//i:
break
ans.append(n//i)
i+=1
if len(ans)==0:
print(2)
print("0 1")
continue
for i in range(ans[-1]-1,-1,-1):
ans.append(i)
print(len(ans))
print(" ".join(map(str,ans[::-1])))
D problem
I thought D was easier than C. Just implement it. It took a long time because $ a, b, c $ appeared in the question sentence and I was confused with the alphabet.
To briefly summarize the problem statement, in addition to the fact that passwords containing the same alphabet can be regarded as the same password, passwords of ○, △, □ include the same alphabet between ○, △ and between △, □. If the same alphabet is included in, ○, △, □ can be regarded as the same password.
Therefore, if you think of ** the same set of passwords as **, you can count the number of sets in the disjoint set system **, so you can think of Union Find.
As long as they contain the same alphabet, we will look at each password to see if it contains the alphabets $ a $ ~ $ z $. Then save it as $ ca [i]: = $ (an array of password indexes containing the alphabet $ i $). Then, you only have to unite all the elements in each array, so you can unite the elements (indexes) before and after ** in that array **. If you do this in any alphabet and then call the group function, the size of the group will be the answer. Also, if you separate the loop that stores in the array and the loop that unites, you can avoid confusion in the implementation.
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 endings)、のどちら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; //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]].PB(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 n;cin>>n;
UnionFind uf(n);
vector<vector<ll>> alp(26);
REP(i,n){
string s;cin>>s;
vector<bool> ca(26);
FORA(i,s){
ca[ll(i-'a')]=true;
}
REP(j,26){
if(ca[j])alp[j].PB(i);
}
}
REP(i,26){
ll l=SIZE(alp[i]);
if(l==0 or l==1)continue;
REP(j,l-1){
uf.unite(alp[i][j],alp[i][j+1]);
}
}
uf.grouping();
cout<<SIZE(uf.group)<<endl;
}
E problem
I will not upsolve this time because I made the implementation buggy and withered. The solution is described below.
** Since it is a parenthesis string, it is a condition that it is always 0 or more and the last element is 0 when the cumulative sum is taken with (+1,) as -1 **. Also, by rewriting the parentheses at the cursor position, ** the cumulative sum after that position changes uniformly in the range of -2 to 2 **. You also need to find the maximum nesting depth when the parenthesized sequence holds, which is ** the maximum of the cumulative sums **.
Therefore, it can be solved by having the cursor position, the current character string, and the two segment trees of RMQ (min) and RMQ (max) for updating the interval. However, I don't have a seg tree, so I made it a bug. I'm thinking of using an improved version of the Seg tree provided by ACL or someone else's Seg tree, but it's not easy to implement. Maybe I will maintain it when I feel like it.
After the F problem
I will skip this time.
Recommended Posts