Codeforces Round # 652 (Div. 2) Bacha Review (8/24)
This time's results
Impressions of this time
This time, I feel that I was able to solve it as I wanted. However, the speed is still insufficient, so I would like to ** improve the sense of solution **.
Problem A
Looking back at the problem, thinking that it would be good if there were parallel sides, it was said that there should be at least one side parallel to the $ X $ axis and parallel to the $ Y $ axis, so the number of sides is four. "YES" was output only when it was a multiple of. I passed it through the contest with a graphic intuition, but it is easy to prove if you pay attention to the central angle.
A.py
for i in range(int(input())):
n=int(input())
print("YES"if n%4==0 else "NO")
Problem B
It seems that it was melting at a considerably faster speed than the surroundings. However, I am sorry because I was a little lost in the implementation. For (binary) ** strings, it is especially important to experiment with samples to get a feel for them **.
Since either of the two adjacent characters "10" is erased, ** continuous 0 at the left end and continuous 1 at the right end cannot be erased ** (I think it is easy to understand by looking at the first sample) I will.). Therefore, I tried to save the number of such elements in $ l and r $. Also, if ** all elements are included in any contiguous part (✳︎) **, it cannot be shortened, so the given character string is output as it is.
Also, if you ignore the continuous part of the left end and the right end, the following character string will appear. (Since the pattern of (✳︎) is excluded, one or more 1's will always appear at the left end and one or more 0's will appear at the right end.)
11…00
Such a string can be finally left in the 10 state by adjusting the order of the characters to be erased. Here, ** if the lengths are the same, they are smaller in dictionary order **, so it is best to erase 1s and leave 0s, and the character string to be output is (continuous 0s at the left end) +0. + (Continuous 1) at the right end.
B.py
for i in range(int(input())):
n=int(input())
s=input()
if all([i=="1" for i in s]) or all([i=="0" for i in s]):
print(s)
continue
#l,r must be
l,r=-1,n
for i in range(n):
if s[i]=="1":
l=i
break
for i in range(n-1,-1,-1):
if s[i]=="0":
r=i
break
if l>r:
print(s)
continue
print(s[:l]+"0"+s[r+1:])
C problem
Consider maximizing the happiness of everyone. At this time, I thought about ** greedy algorithm ** while thinking about using elements that are as large as possible for both max and min. That is, consider that ** small elements are consumed as much as possible ** to increase min, and ** large elements are consumed as little as possible ** to increase max. That is, you can think as follows.
Arrange $ a \ _i $ and $ w \ _i $ in descending order. For each $ w \ _i $ max, select and remove the largest remaining element. Then, select and remove $ w \ _i-1 $ pieces from the remaining elements in ascending order. At this time, min is the smallest element. By doing this, max can select the largest $ k $ pieces ** in ** $ a \ _i $, and ** consume the smallest elements as much as possible ** first. You can aim for maximization with.
However, what you should be careful about here is when ** $ w \ _i = 1 $ **. At this time, ** max and min match **, so by selecting a large element, you can select twice the happiness of that element. Therefore, when $ w \ _i = 1 $, select a large element in advance.
C.py
from collections import deque
for _ in range(int(input())):
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
a=deque(a)
w=list(map(int,input().split()))
w.sort(reverse=True)
#Process 1 first
ans=0
for i in range(w.count(1)):
ans+=2*a.popleft()
for i in range(k-w.count(1)):
p=a.popleft()
ans+=p
#print(p)
for j in range(w[i]-1):
p=a.pop()
if j==0:
ans+=p
#print(p)
print(ans)
D problem
For the time being, I thought ** by drawing a diagram ** to know what kind of tree it is. At this time, the vertices increased in the order of red → yellow → blue → green → red, and I understood that it is a tree that is recursively determined in order from the root (it can also be called a fractal figure).
Also, if you look at claw (a subtree that has three sides from one root), ** claw roots are also included in claw **. Therefore, it is possible to paint only the claw that was created at the $ n $ time, and (the number of roots of the claw that was created at the $ n $ time) $ \ times $ 4 is the number of vertices that can be painted yellow. It was (✳︎).
Here, ** it can be recursively determined from the root and ** there are three types of vertex states ** (whether it has no leaves, one leaf, or three leaves). Focusing on, it is easy to implement if you think of it as dp. Therefore, define DP as follows:
$ dp [i] [j]: = $ (How many vertices are in the state $ j $ by the $ i $ first attempt)
However, it does not have a leaf when $ j = 0 $, has one leaf when $ j = 1 $, and has three leaves when $ j = 2 $.
At this time, the change in DP is as follows. (If the transition of DP is difficult to understand like this problem, it is easy to understand by tabulating the transition **.)
When this is transcribed in the code, it looks like this:
dp[i][0]+=dp[i-1][0]
dp[i][1]+=dp[i-1][0]
dp[i][0]+=dp[i-1][1]*2
dp[i][2]+=dp[i-1][1]
dp[i][2]+=dp[i-1][2]
Also, if you use (✳︎), $ (dp [i] [2] -dp [i-1] [2]) \ times 4 $ will be the answer, but ** $ n $ the claw that was created Other than that can be painted **, so some of the samples did not pass. Considering the figure below, if you apply the $ n $ th claw, you can apply the ** $ n-3 $ th claw among the higher claws **.
Therefore, the claws that can be painted in the Rooted Dead Bush whose level is $ n $ are "($ n $ claws) + ($ n-3 $ claws) + ($ n-6 $). It will be the claw) +… "that was made the second time.
Also, in terms of the amount of calculation **, it is not enough to calculate the DP every time **, so the ** DP array up to $ 2 \ times 10 ^ 6 $ is precalculated **, and the (index) of the DP array The ** cumulative sum (for each value of $ mod \ 3 $) must also be prepared in the precalculation **.
In addition, the DP pre-calculation seemed to use too much memory in my implementation and became MLE, so I rewrote it to ** C ++ and took MLE **.
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
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n=2000000;
vector<vector<ll>> dp(n,vector<ll>(3,0));
dp[0][0]=1;
FOR(i,1,n-1){
dp[i][0]+=dp[i-1][0];
dp[i][1]+=dp[i-1][0];
dp[i][0]+=dp[i-1][1]*2;
dp[i][2]+=dp[i-1][1];
dp[i][2]+=dp[i-1][2];
dp[i][0]%=MOD;
dp[i][1]%=MOD;
dp[i][2]%=MOD;
}
vector<ll> ans(n,0);
REP(i,3){
if(i!=0){
ans[i]+=(MOD+dp[i][2]-dp[i-1][2])*4;
ans[i]%=MOD;
}
for(ll j=i;j<n-3;j+=3){
ans[j+3]+=ans[j];
ans[j+3]+=(MOD+dp[j+3][2]-dp[j+2][2])*4;
ans[j+3]%=MOD;
}
}
ll t;cin>>t;
REP(i,t){
cin>>n;
cout<<ans[n-1]<<endl;
}
}
After the E problem
I will skip this time
Recommended Posts