Codeforces Round # 672 (Div. 2) Bacha Review (10/16)
This time's results
Impressions of this time
This time, I was able to solve it without issuing WA (although it took time), thanks to the fact that I proceeded while organizing the problem settings. Also, the D problem was troublesome to press down and speed up, so if I handled it as a set, it would be dangerously TLE (1996ms / 2000ms).
There were many people who upsolved C2 by looking at the standings of friends, but I didn't feel motivated. I haven't upsolved for two days in a row since yesterday, so I'll try to upsolve after tomorrow so that I don't get into this habit.
Problem A
Number of inversions with BIT! ?? However, that was not the case. ** The maximum value of the number of inversions ** is $ \ frac {n (n-1)} {2} $ only when the elements are arranged in descending order **, so determine whether it will be the maximum value. .. Also, note that when there are multiple same elements, it will not be $ \ frac {n (n-1)} {2} $, but kindly there is a case in the sample.
A.py
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
if a==sorted(a,reverse=True) and len(set(a))==n:
print("NO")
else:
print("YES")
Problem B
At first I misunderstood the problem and it was dangerous (I was thinking that the same element because arbitrary bits are the same).
If the $ k $ bits of $ a \ _i and a \ _j $ are $ a \ _ {ik} and a \ _ {jk} $, respectively, then $ a \ _ {ik} $ & $ a \ _ { jk} $, $ a \ _ {ik} \ oplus a \ _ {jk} $ looks like this: (** Bit by bit! **)
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Therefore, $ a \ _i $ & $ a \ _ j \ geqq a \ _i \ oplus a \ _j $ holds for $ (a \ _ {ik}, a \ _ {jk}) = (0,0), It will be (1,1) $. Therefore, when there is a bit (MSB) ** that stands for the first time from the bit on ** of $ a \ _i $, the number that satisfies $ a \ _i $ is the same number of MSBs ($ ). Because $ is a positive number, so the bit is always set).
Therefore, each $ a \ _ {i} $ is classified by MSB, and when there are $ x $ such $ a \ _ {i} $, there are $ \ _ x C \ _2 $ combinations. Exists. The answer is to find the sum of these.
B.py
from collections import Counter
for _ in range(int(input())):
n=int(input())
x=[0 for i in range(30)]
l=list(map(int,input().split()))
for i in l:
for j in range(29,-1,-1):
if (i>>j)&1:
x[j]+=1
break
ans=0
for i in x:
if i>1:
ans+=(i*(i-1)//2)
print(ans)
C1 problem
It has already appeared in Kodofo. However, I made a mistake in the subscript. Are you stupid ...?
Since you only need to find the maximum value of the (special) sum of the ** subsequence **, whether it is-or + is determined by-or + of the previously selected element. Therefore, consider the following DP.
$ dp [i] [j]: = $ (maximum value of (special) sum of subsequences selected from up to $ i $ th number, but last selected number when $ j = 0 $ When is-and $ j = 1 $, the last selected number is +)
The transition is as follows. The transition of subsequences can be roughly considered in the following three ways. It is necessary to pay attention only to the case of-or +.
(1) When the $ i + 1 $ th element is not selected
(2) When selecting the $ i + 1 $ th element instead of the first time
(3) When selecting the $ i + 1 $ th element for the first time
If you find the above maximum values in order, $ max (dp [n-1]) $ is the answer.
C.py
inf=10**12
import sys
input = sys.stdin.readline
for _ in range(int(input())):
n,q=map(int,input().split())
a=list(map(int,input().split()))
dp=[[-inf,-inf] for i in range(n)]
dp[0]=[-inf,a[0]]
for i in range(n-1):
dp[i+1][0]=dp[i][0]
dp[i+1][1]=dp[i][1]
dp[i+1][0]=max(dp[i+1][0],dp[i][1]-a[i+1])
dp[i+1][1]=max(dp[i+1][1],dp[i][0]+a[i+1])
dp[i+1][1]=max(dp[i+1][1],a[i+1])
print(max(dp[n-1]))
#print(dp)
C2 problem
I will skip this time.
D problem
I feel that it should have been solved at high speed, so I would like to improve the mounting power.
There are $ n $ closed intervals ** Check if the ends of each section overlap **. In other words, by ** seating only at the end of the section , you only need to consider at most $ 2n $ coordinates. Therefore, $ k $ intervals that overlap at least one coordinate can be selected as the subject interval ( paraphrase of the subject! **).
Here, there are times when you can select ** a combination of the same section with multiple coordinates ** (✳︎), so you need to be careful. For example, the red and yellow parts in the figure below ($ k = 3 $).
Also, ** First of all, I want to think greedily **, so I will look at them in ascending order of coordinates. Here, assuming that there are $ x $ already selected sections and $ y $ sections selected for the first time at a certain coordinate, "how to select a section that has not been selected yet" is changed from "how to select any section that can be selected here" to ". The total number is $ _ {x + y} C_k-_xC_k $, excluding "How to choose from only the sections that have already been selected" (It took a long time to notice, but a simple ** inclusion principle * *is). Therefore, if you manage the interval containing each coordinate, you can calculate the combination with $ O (1) $ (the precalculation of the combination is $ O (n) $).
Therefore, the implementation is as follows (** Implementation is summarized! **).
nowseg: set that has the information of the section including the coordinates you are looking at as (coordinates at the right end of the section, index) nexseg: Map that has the information of the section that has not been seen yet, with the left end of the section as the key and (the coordinates of the right end of the section, the index) as the value. coordinates: set with possible interval ends (because I wanted to keep it in ascending order and skip the implementation of sitting pressure)
This way, at each coordinate $ i $
(1) Set the size of nowseg to $ x $ and the size of nexseg [i] to $ y $, and find the number of new combinations of intervals that can be created by combination calculation. ② Add all elements of nexseg [i] to nowseg ③ Delete only the coordinates of the right end of the section in nowseg that are $ i $ (check in order from the first element of nowseg)
It can be easily implemented by performing the operations in the order of.
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 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 998244353 //10^9+7:Congruence law
#define MAXR 300002 //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
template<ll mod> class modint{
public:
ll val=0;
//constructor
modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
//Copy constructor
modint(const modint &r){val=r.val;}
//Arithmetic operator
modint operator -(){return modint(-val);} //unary
modint operator +(const modint &r){return modint(*this)+=r;}
modint operator -(const modint &r){return modint(*this)-=r;}
modint operator *(const modint &r){return modint(*this)*=r;}
modint operator /(const modint &r){return modint(*this)/=r;}
//Assignment operator
modint &operator +=(const modint &r){
val+=r.val;
if(val>=mod)val-=mod;
return *this;
}
modint &operator -=(const modint &r){
if(val<r.val)val+=mod;
val-=r.val;
return *this;
}
modint &operator *=(const modint &r){
val=val*r.val%mod;
return *this;
}
modint &operator /=(const modint &r){
ll a=r.val,b=mod,u=1,v=0;
while(b){
ll t=a/b;
a-=t*b;swap(a,b);
u-=t*v;swap(u,v);
}
val=val*u%mod;
if(val<0)val+=mod;
return *this;
}
//Equivalence comparison operator
bool operator ==(const modint& r){return this->val==r.val;}
bool operator <(const modint& r){return this->val<r.val;}
bool operator !=(const modint& r){return this->val!=r.val;}
};
using mint = modint<MOD>;
//I / O stream
istream &operator >>(istream &is,mint& x){//Do not add const to x
ll t;is >> t;
x=t;
return (is);
}
ostream &operator <<(ostream &os,const mint& x){
return os<<x.val;
}
//Exponentiation
mint modpow(const mint &a,ll n){
if(n==0)return 1;
mint t=modpow(a,n/2);
t=t*t;
if(n&1)t=t*a;
return t;
}
//Calculation of binomial coefficient
mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];
//Creating a table
void COMinit() {
fac[0]=fac[1]=1;
finv[0]=finv[1]=1;
inv[1]=1;
FOR(i,2,MAXR){
fac[i]=fac[i-1]*mint(i);
inv[i]=-inv[MOD%i]*mint(MOD/i);
finv[i]=finv[i-1]*inv[i];
}
}
//Calculation part
mint COM(ll n,ll k){
if(n<k)return 0;
if(n<0 || k<0)return 0;
return fac[n]*finv[k]*finv[n-k];
}
signed main(){
//Code for speeding up input
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
COMinit();
ll n,k;cin>>n>>k;
map<ll,vector<pair<ll,ll>>> nexseg;
set<pair<ll,ll>> nowseg;
set<ll> coordinates;
REP(i,n){
ll l,r;cin>>l>>r;
nexseg[l].PB(MP(r,i));
coordinates.insert(l);
coordinates.insert(r);
}
//Scan coordinates from left
//Originally new addition(Check the number)→ Check for missing items
//Then delete
mint ans=0;
FORA(i,coordinates){
//cout<<1<<endl;
ll x,y;x=SIZE(nowseg);
if(nexseg.find(i)==nexseg.end()){
y=0;
ans+=0;
}else{
y=SIZE(nexseg[i]);
FORA(j,nexseg[i]){
nowseg.insert(j);
}
ans+=(COM(x+y,k)-COM(x,k));
}
//cout<<x<<" "<<y<<" "<<ans<<endl;
auto j=nowseg.begin();
//cout<<j->F<<" "<<j->S<<endl;
while(j!=nowseg.end()){
//cout<<1<<endl;
if(j->F==i){
j=nowseg.erase(j);
}else{
break;
}
}
}
cout<<ans<<endl;
}
E problem
I will skip this time.
Recommended Posts