[PYTHON] Codeforces Round # 612 (Div. 2) Bacha Review (10/2)
This time's results
Impressions of this time
This time, ** I couldn't figure out the problem to throw away **, and ** I was overwhelmed by the appearance of the implementation game **.
Also, I couldn't debug ** from the viewpoint of whether there is a problem in consideration or implementation, so I will make use of it with today's yukicoder.
Problem A
** I misread what should be output at the beginning **.
Change the person next to A to A at each time and repeat this until it doesn't change, and at each time at least one person will change to A, so write a program with stupid $ O (N ^ 2) $ can do.
A.py
for _ in range(int(input())):
n=int(input())
s=[i=="A" for i in list(input())]
tim=[s]
ans=0
while True:
t=[s[0]]
for i in range(n-1):
if tim[-1][i]==1:
t.append(True)
else:
t.append(tim[-1][i+1])
#print(s,t)
if tim[-1]==t:
break
ans+=1
tim.append(t)
#print(s,t)
print(ans)
Problem B
It was the most difficult problem I solved this time. If you do not write an efficient program, it will be dropped by a constant multiple. I regret that I didn't usually have that much awareness.
(In the following, we are discussing the condition that ** there is no card with the same characteristics **.)
First, I wanted to look at each feature one by one recursively, but it's difficult because I can't think of each feature independently. I'm getting stuck here, but if I look at the problem calmly, I've reached the line where $ O (KN ^ 3) $ can be foolish, and $ N $ is about 1500 at the maximum, so $ O (N ^ 2) I noticed that a program of about $ would be in time (** If you get stuck in a policy, consider a straightforward solution! **).
Therefore, consider deciding on two cards. Then you can see that ** the remaining cards are uniquely determined **. In other words, for a certain feature, if the two decided cards are equal, the remaining cards are equal, and if the two decided cards are different, the remaining card is also another feature. Therefore, you should consider ** whether the remaining cards are included in the given card . Also, if the given card is saved in the set structure, $ O (k \ log {n}) $ is used to determine whether it is included in $ O (k) $ to find the cards that can be combined. So, if you put it together, you can implement it with $ O (k \ log {n}) $. Therefore, the total amount of calculation is $ O (n ^ 2k \ log {n}) $, and $ n ^ 2k \ log {n} $ is about $ 10 ^ 8 $ ~ $ 10 ^ 9 $ at the maximum. Even in C ++, it's just barely enough, so " lighten the judgment **" and "because it's three letters $ S, E, T $, it's ** converted to a cubic number (implementation is easy if it's a quaternary number) **. , "If you ask for a set of three cards, they will be duplicated, but at this time you will be asked for three times the answer, so ** no need to judge duplicates **, (the number of things that meet the conditions) $ \ div 3 $ If you use "Good thing", you can speed up by a constant number of times, and you can pass it with a margin ($ 732ms $).
✳︎… set and map can be inserted with $ O (\ log {n}) $, but ** some elements are not $ O (\ log {n}) $ ** Caution is required. For example, if the character string is $ l $ in length, the operation will be slowed down by the length of $ O (l \ log {n}) $ and the character string. Therefore, when dealing with a character string like this one, it is necessary to pay attention to the analysis of the amount of calculation.
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
ll k;
vector<ll> cards;
//Returns the i-th number
inline ll quadrant(ll x,ll i){
return ((x>>(2*i))&1)+((x>>(2*i+1))&1)*2;
}
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n>>k;
//Convert vector to quaternary!(Real binary number)
cards=vector<ll>(n);
map<ll,ll> ma;
vector<ll> po(k);
REP(i,k)po[i]=1LL<<(2*i);
REP(j,n){
string s;cin>>s;
ll calc=0;
REP(i,k){
if(s[i]=='S'){
calc+=1*po[i];
}else if(s[i]=='T'){
calc+=2*po[i];
}else{
calc+=3*po[i];
}
}
cards[j]=calc;
ma[cards[j]]=j;
}
//Stop managing candidates with cand(Just divide by 3)
//Pruning?
ll ans=0;
REP(i,n){
FOR(j,i+1,n-1){
ll ne=0;
REP(l,k){
ll temp=quadrant(cards[i],l)*quadrant(cards[j],l);
if(temp==1 or temp==6){
ne+=po[l];
}else if(temp==3 or temp==4){
ne+=2*po[l];
}else{
ne+=3*po[l];
}
}
if(ma.find(ne)!=ma.end()){
ans++;
}
}
}
cout<<ll(ans/3)<<endl;
}
C problem
Even though it is a DP, the implementation has become heavy. That's bad ...
First, since $ n $ is 100, read the question sentence with an awareness of ** $ O (n ^ 3) $. Also, the complexity is determined by ** how many adjacent numbers have different evens and odds **, so consider ** deciding in order from the front **. Furthermore, since only 1 ~ $ n $ comes out and only ** odd numbers need to be known **, $ [\ frac {n} {2}] $ even numbers and $ n-[\ frac {n } {2}] $ Odd numbers should be lined up.
Here, when deciding from the front, it is ** difficult to decide greedily **, but when you look at the $ i $ th element, how many even numbers and odd numbers are used up to that point ** and ** I found it not difficult to find the minimum complexity if I saved the evenness ** of the last element. You can also easily see that this DP is $ O (n ^ 3) $. Therefore, set the DP as follows.
$ dp [i] [j] [k]: = $ (Determine up to the $ i $ th element, use only $ j $ even numbers, and divide the $ i $ th element by 2 to get the remainder of $ k $ Minimum complexity of time)
Therefore, considering the transition from $ p [i-1] $ to $ p [i] $, it becomes as follows. Also, the transition should take $ min $ instead of $ = $, but it is written like this so as not to be redundant.
(1) When $ p [i]! = 0 $ and $ p [i] $ is an even number
When $ p [i-1] $ is even, the evenness does not change, so $ dp [i] [j + 1] [0] = dp [i-1] [j] [k] $.
When $ p [i-1] $ is odd, the evenness changes, so $ dp [i] [j + 1] [0] = dp [i-1] [j] [k] + 1 $.
(2) When $ p [i]! = 0 $ and $ p [i] $ is odd
When $ p [i-1] $ is odd, the evenness does not change, so $ dp [i] [j + 1] [1] = dp [i-1] [j] [k] $.
When $ p [i-1] $ is even, the even number changes, so $ dp [i] [j + 1] [1] = dp [i-1] [j] [k] + 1 $.
(3) When $ p [i] = 0 $
Since $ p [i] $ can have any number of even and odd numbers, it is sufficient to combine the transitions of both (1) and (2).
From the above, the transition can be considered, and the final value we want to find is the minimum value when ** $ i = n-1, j = n // 2 $ **, so $ min (dp [-1] [ n // 2]) Just output $.
C.py
n=int(input())
p=list(map(int,input().split()))
inf=10**12
dp=[[[inf,inf] for j in range(101)] for i in range(n)]
if p[0]!=0:
if p[0]%2==0:
dp[0][1][0]=0
else:
dp[0][0][1]=0
else:
dp[0][1][0]=0
dp[0][0][1]=0
for i in range(1,n):
for j in range(101):
for k in range(2):
if dp[i-1][j][k]==inf:
continue
if p[i]!=0:
if p[i]%2==0:
if k==0:
dp[i][j+1][0]=min(dp[i-1][j][k],dp[i][j+1][0])
else:
dp[i][j+1][0]=min(dp[i-1][j][k]+1,dp[i][j+1][0])
else:
if k==0:
dp[i][j][1]=min(dp[i-1][j][k]+1,dp[i][j][1])
else:
dp[i][j][1]=min(dp[i-1][j][k],dp[i][j][1])
else:
if k==0:
dp[i][j+1][0]=min(dp[i-1][j][k],dp[i][j+1][0])
else:
dp[i][j+1][0]=min(dp[i-1][j][k]+1,dp[i][j+1][0])
if k==0:
dp[i][j][1]=min(dp[i-1][j][k]+1,dp[i][j][1])
else:
dp[i][j][1]=min(dp[i-1][j][k],dp[i][j][1])
print(min(dp[-1][n//2]))
D problem
This time, there were many problems with relatively heavy implementation. However, I don't think the idea itself is so twisted. I think it will be strong if I can write this innocently, so I will make an effort.
In the following, the vertices of the subtree are implicitly described as $ a \ _j $ except for $ a \ _i $ contained in the subtree whose vertices are $ a \ _i $ and $ a \ _i $. Please forgive me for the sake of simplification of the explanation.
Configure $ a \ _i $ so that for a vertex $ i $ there are only $ c \ _i $ less than the number $ a \ _i $ written in its subtree elements. think. Here, it is self-evident that ** solve using DFS because we need information on the subtree **. Also, for the leaf vertices, if $ c \ _i = 0 $, then $ a \ _i = 1 $ should be set, and if $ c \ _i> 0 $, this is not possible, so NO should be output. .. Also, ** if the vertex $ i $ is not a leaf, it is necessary to merge multiple subtrees whose vertices are their children **, but when merging, $ a \ _j $ was put together in one array. Sort on. Under this source, we will insert $ a \ _i $ into this array, but since it has been sorted, we will insert it as the value between the ** $ c \ _i-1 $ th element and the $ c \ _i $ th element * *is needed. Also, if there is a difference of more than 1 between the $ c \ _i-1 $ th element and the $ c \ _i $ th element, it is only inserted between them, but if they are equal, the $ c \ _i + 1 $ th and subsequent elements are inserted. The element must be +2 before insertion. Also, ** Be careful not to break the magnitude relationship of $ a \ _j $ in the subtree you have already found **.
With the above considerations, the basic policy is perfect, but I will also touch on the implementation. Since it is not difficult to create a tree by assuming a directed adjacent graph and the output is not difficult, we will consider only the implementation of DFS.
First, we need to return an array of $ a \ _j $ values in a fixed subtree to the parent vertices. Also, in the final output, ** it is necessary to correspond to the index of each vertex **, so the return value is returned to the array of (value, index) pairs.
Here, prepare $ ret $ as an array that stores the information of arbitrary $ a \ _j $. You can insert the elements of the array returned by dfs with the child vertices as subtrees into this $ ret $. After inserting, sort (in ascending order of value).
Next, consider determining $ a \ _i $ from $ ret $. Also, it should be noted that ** may not be true in the first place **.
① When $ c \ _i > (total number of a \ _j $) Since $ a \ _i $ that satisfies this condition does not exist, check it as not valid. The return value should be an empty array.
② When $ c \ _i \ = (total number of a \ _j $) ** Insert +1 into the largest element ** and then return the array. Also, if $ c \ _i = 1 $, 1 should be returned.
③ When $ c \ _i = 0 $ I want to insert the smallest element with -1 and return it, but ** the smallest element is 1, so by adding +1 to the whole and inserting 1 **, the magnitude relationship does not change. You can insert it.
④ At other times You need to insert it in the middle. As mentioned in the discussion, the element should be larger than the $ c \ _i $ th element and smaller than the $ c \ _i + 1 $ th element (✳︎). Therefore, if ($ c \ _i $ th element) +1 <($ c \ _i + 1 $ th element), then $ a \ _i = $ ($ c \ _i $ th element) +1. It's fine. In other cases, by adding +2 to the elements after $ c \ _i + 1 $ and then adding the original ($ c \ _i + 1 $ th element) +1 to ** $ a \ _j $ You can insert $ a \ _i $ without breaking the magnitude relationship of **.
By repeating returning the updated ret above, you can get $ a \ _i $ merged entirely in the calling function, and you can output this.
(✳︎)… It may be equal to $ c \ _i + 1 $ th, but it is better to make it ** elements that are included in the same subtree and have a magnitude relationship defined are not equal ** Do not step on the case.
Regarding the amount of calculation, the dfs function is called up to $ n $ times, and each amount of calculation is $ O (n) $, so the total amount is $ O (n ^ 2) $, which is a sufficient margin.
D.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
vector<vector<ll>> tree;
vector<ll> cost;
bool check;
//Returns as an index / value pair(Value, index)
//Make it all different!(Processing when wearing is troublesome)
//From the middle+So that the relationship doesn't break!
vector<pair<ll,ll>> dfs(ll v){
vector<pair<ll,ll>> ret={};
FORA(i,tree[v]){
FORA(j,dfs(i)){
ret.PB(j);
}
}
sort(ALL(ret));
//cout<<cost[v]<<SIZE(ret)<<endl;
if(cost[v]>SIZE(ret)){
check=true;
return {};
}else if(cost[v]==SIZE(ret)){
if(SIZE(ret)==0){
ret.PB(MP(1,v));
return ret;
}else{
ret.PB(MP(ret[SIZE(ret)-1].F+1,v));
return ret;
}
}else if(cost[v]==0){
FOR(i,cost[v],SIZE(ret)-1){
ret[i].F++;
}
ret.PB(MP(1,v));
return ret;
}else{
ll x=ret[cost[v]].F;
if(ret[cost[v]-1].F+1<ret[cost[v]].F){
ret.PB(MP(x-1,v));
return ret;
}else{
FOR(i,cost[v],SIZE(ret)-1){
ret[i].F++;
ret[i].F++;
}
ret.PB(MP(x+1,v));
return ret;
}
}
}
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
check=false;
ll n;cin>>n;
tree=vector<vector<ll>>(n);
cost=vector<ll>(n);
ll root;
REP(i,n){
ll p,c;cin>>p>>c;p--;
if(p!=-1){
tree[p].PB(i);
}else{
root=i;
}
cost[i]=c;
}
vector<pair<ll,ll>> d=dfs(root);
vector<ll> ans(n);
FORA(i,d){
ans[i.S]=i.F;
}
if(check){
cout<<"NO"<<endl;
return 0;
}
cout<<"YES"<<endl;
REP(i,n){
if(i!=n-1)cout<<ans[i]<<" ";
else cout<<ans[i]<<endl;
}
}
After the E problem
I will skip this time. I couldn't secure enough time for consideration because my computer wasn't working well.
Recommended Posts