[PYTHON] Codeforces Round # 613 (Div. 2) Bacha Review (10/1)
This time's results
Impressions of this time
Is it OK as a grade? ** I was able to solve the level range problems that I had to solve **, which is highly evaluated by me. However, I regret that I couldn't fully consider the E problem just by warming the chair in the remaining hour **.
(I will skip the E problem this time because the policy did not come out immediately.)
Problem A
If you want to go to the left as much as possible, you will reach the coordinates of-(the number of $ L $ in the string), and if you go to the right as much as possible, you will reach the coordinates of (the number of $ R $ in the string). Also, ** all the coordinates in between can be reached **, so the answer is (the number of $ R $ in the string) + (the number of $ L $ in the string) + 1.
(** Check only both ends of the range! **)
A.py
n=int(input())
s=input()
print(s.count("L")+s.count("R")+1)
Problem B
I missed various problem sentences. It is a reflection. Specifically, it should be noted that Adel can select ** continuous subsequences ** and ** cannot select the whole **.
Here, the deliciousness of the cake that Yasser chooses is only to find the sum by $ O (N) $, so ** Adel finds the maximum value ** (✳︎) in the continuous subsequence that can be selected, and that value is If it is less than the total, "YES" should be output, otherwise "NO" should be output.
If the maximum value in a continuous subsequence is $ dp [i]: = $ (the maximum value of the partial sum of continuous subsequences ending in $ i $ th), then ** $ i-1 $ th is the end. It can be calculated by DP just by considering whether or not to attach it to the continuous subsequence that has as. However, when performing a normal DP on a given sequence, it does not meet the condition that ** the whole cannot be selected **.
So, in other words, you can respond by saying ** you don't have to select the first element and the last element at the same time **. Therefore, $ dp1 $ performs DP to find the maximum value of the sum when a continuous subsequence is selected from $ n $ -1st element from the 1st element, and $ dp2 $ is $ from the 2nd element. Performs DP to find the maximum value of the sum when a continuous subsequence is selected from the n $ th element. The maximum value obtained by these two DPs is the maximum value in (✳︎).
B.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
inf=10**15
dp1=[-inf]*(n-1)
dp1[0]=a[0]
for i in range(1,n-1):
dp1[i]=max(dp1[i-1]+a[i],a[i])
dp2=[-inf]*(n-1)
dp2[0]=a[1]
for i in range(2,n):
dp2[i-1]=max(dp2[i-2]+a[i],a[i])
if max(dp1+dp2)<sum(a):
print("YES")
else:
print("NO")
C problem
First, from the condition that $ LCM (a, b) = X $, ** $ a and b $ are divisors of $ X $ **, respectively. Also, due to the constraint of the problem, ** all divisors can be searched **, so $ a $ is used as a divisor of $ X $ to search all.
Consider the smallest $ b $, with ** $ a $ being fixed **. At this time, if $ GCD (a, b) = 1 $, $ b = \ frac {X} {a} $ will be the minimum $ b $. In the case of $ GCD (a, b) \ neq 1 $, if $ LCM (a, b) = X $ is transformed, $ b = \ frac {X} {\ frac {a} {GCD (a, b)}} It will be $, but $ \ frac {a} {GCD (a, b)} $ is also a divisor of $ X $, so you don't need to look it up ** (). Therefore, you can find the one with the smallest $ max (a, b) $ in any $ a $.
✳︎… I didn't do the proof for $ GCD (a, b) \ neq 1 $ while I was solving it. I can't help it because I was impatient, but it's not obvious, so I'll try to ** prove it in my head **.
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
vector<ll> divisors;//Array to store divisors
void make_divisors(ll n){
FOR(i,1,sqrt(n)){
if(n%i==0){
divisors.PB(i);
if(i!=n/i){
divisors.PB(n/i);
}
}
}
}
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll x;cin>>x;
make_divisors(x);
//Make the first element larger
pair<ll,ll> ans=MP(INF,INF);
FORA(a,divisors){
if(gcd(a,x/a)!=1)continue;
pair<ll,ll> ans_sub;
if(a>x/a){
ans_sub=MP(a,x/a);
}else{
ans_sub=MP(x/a,a);
}
if(ans_sub.F<ans.F){
ans=ans_sub;
}
}
cout<<ans.F<<" "<<ans.S<<endl;
}
D problem
I was disappointed that I couldn't solve a similar problem with HUPC, so I'm very happy to be able to revenge this time.
First, I found it difficult to decide from the bits above ** and greedily make it smaller **. However, in the discussion ** consider the maximum value for each bit ** and we see the following (the bit-by-bit calculation of $ \ because $$ $ \ oplus $ is independent). In other words, when the $ i $ bit of $ X $ is 0, the $ (a \ _i \ oplus X) \ _ {max} $ of the $ i $ bit is the $ i $ bit of ** $ a $. When the number to be 1 and the xor of $ X $ are taken, it becomes $ 2 ^ i $, and when the $ i $ bit of $ X $ is 1, the relationship is reversed.
Therefore, ** divide the number that maximizes the $ i $ bit of $ X $ from 0 or 1 when viewed from the upper bit **, and recursively $ i-1 even for the set of divided numbers. Just look at the $ bit and divide it. Also, since what we want to finally find is the minimum $ (a \ _ i \ oplus X) \ _ {max} $, the return value of the recursive function is $ min $ ($ i $ set of numbers with 0 bits). As a result of calculating the $ i-1 $ bit and after, the result of calculating the $ i-1 $ bit and after for the set of numbers whose $ i $ bit is 0) + $ 2 ^ i $ It's fine. Furthermore, if the ** $ i $ bits of the set of numbers given to the recursive function are all the same **, by giving the same bits as that bit, the maximum $ (a \ _ i \ oplus X) of the $ i $ bits ) \ _ {Max} $ becomes 0, and it is sufficient to return the result of calculating the $ i-1 $ and subsequent bits without performing division. Also, if $ i = 0 $, the recursion is terminated.
If you implement the above recursive function, you can find the minimum $ (a \ _ i \ oplus X) \ _ {max} $ and output it. Also, I was worried about the amount of calculation of the recursive function, but since it divides each time it is recursive, each element is called only once at the ** $ i $ bit **, $ O (\ log {a \ \ It can be suppressed by _ {max}} n) $ and operates fast enough.
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
ll rec(vector<ll> vec,ll ind){
ll ret=0;
vector<ll> vec0,vec1;
FORA(i,vec){
if((i>>ind)&1){
vec0.PB(i);
}else{
vec1.PB(i);
}
}
if(SIZE(vec0)==0){
if(ind==0)return 0;
return rec(vec1,ind-1);
}
if(SIZE(vec1)==0){
if(ind==0)return 0;
return rec(vec0,ind-1);
}
//Neither is 0(Return the smaller one)
//+2^i
if(ind==0)return 1;
return min(rec(vec0,ind-1),rec(vec1,ind-1))+(1<<ind);
}
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n;cin>>n;
vector<ll> a(n);REP(i,n)cin>>a[i];
cout<<rec(a,31)<<endl;
}
After the E problem
I will skip this time.
Recommended Posts