[PYTHON] AtCoder Beginner Contest 127 Review of past questions

This time's results

Impressions of this time

I had the correct idea for the E problem and the F problem, but I couldn't make it AC because I couldn't finish the consideration and implementation. Since the D problem can be completed quickly, I try to ** carefully consider and implement it **. Also, the implementation was troublesome for the F problem, but if you organize it, it is not that difficult to implement, so don't forget ** Consideration in the implementation part **.

Problem A

Just make the case carefully.

A.py

a,b=map(int,input().split())
if a>=13:
    print(b)
elif a>=6:
    print(b//2)
else:
    print(0)

B problem

Make a note of each section in turn.

B.py

r,d,x=map(int,input().split())
ans=[x]
for i in range(10):
    ans.append(r*ans[-1]-d)
for i in range(1,11):
    print(ans[i])

C problem

Only the i-th ID card that satisfies $ max (L) \ leqq i \ leqq min (R) $ can pass through all gates with just one card.

This can be proved as follows. When $ i \ <max (L) $, $ L_j = max (L) $ cannot be passed through the jth gate, and when $ i > min (R) $, $ L_j = max ( R) Cannot pass through the jth gate, which is $. Also, when it is $ max (L) \ leqq i \ leqq max (R) $, it is clear that the i-th card can be used for all gates. From the above, I was able to prove it.

C.py

n,m=map(int,input().split())
l,r=[],[]
for i in range(m):
    x,y=map(int,input().split())
    l.append(x)
    r.append(y)
ansl,ansr=max(l),min(r)
print(max(0,ansr-ansl+1))

D problem

Since it has become possible to answer immediately up to the green diff, I would like to devote myself so that I can answer immediately from the water diff.

If you select a card and repeat rewriting, it will become O (MN) and it will obviously not be in time, so consider another method.

Here, I feel like ** I want to increase the number of each card as much as possible **. Also, each card can be rewritten to take any number of $ C_1, C_2,…, C_M $, so ** select the larger $ N $ number from all possible numbers ** I decided to take the policy.

Also, ** Save all possible numbers ($ A_1,… A_N, C_1,…, C_M $) as dict type **, and you can easily calculate by selecting $ N $ in descending order. can do.

answerD.py

from collections import Counter
n,m=map(int,input().split())
d=Counter(list(map(int,input().split())))
for i in range(m):
    b,c=map(int,input().split())
    if c in d:
        d[c]+=b
    else:
        d[c]=b
d=sorted(Counter(d).items(),reverse=True)
check=n
ans=0
for i in d:
    if i[1]<check:
        check-=i[1]
        ans+=(i[0]*i[1])
    else:
        ans+=(i[0]*check)
        print(ans)
        break

E problem

In such a problem (calculate the sum of ** 〇〇, count the number of patterns of 〇〇, etc. **), it is not enough to count all the patterns, so ** you can count the same patterns together. **. I should be able to solve it according to this policy, but I couldn't match it no matter how many times I tried this enumeration. (← ** The cause is the politeness of consideration **. It is necessary to organize it properly when making notes.)

First,|x_i-x_j|+|y_i-y_j|Is determined by the squares of the two pieces, Two squaresKThe pattern that is selected among the squares of the individual pieces is the squares excluding those two squares.(N \times M-2)FromK-2Thinking about choosing a piece of square,$ _{n \times m-2} C _{k-2}$It will be on the street.

Also, how to choose the two pieces to pay attention to$ _{n \times m} C _2 The amount of calculation is large if it is left on the streetO(n \times m)It will not be in time, so we need to put together more patterns. What I want to know here**|x _i-x _j|+|y _i-y _j|The value of the**so**|x _i-x _j|When|y _i-y _j|$の計算は独立にsoきる**こWhenを考慮すれば、それぞれThe value of theのパターンを別々so計算しても良いこWhenがわかります。

(Below, for simplicity|x _i-x _j|I think only at the time of|y _i-y _j|The same is true at the time of.)

Therefore,|x _i -x _j |=kWhenkCorresponds to the value of(x _i,x _j )Consider finding out how many pairs there are. here,1 \leqq x _i ,x _j \leqq NIs$ x _i,x _j Can be different(\because x _i =x _j $At the time of k=Since it is 0, it does not affect the total)So1 \leqq k \leqq N-1It will be. Also, at this time(x _i,x _j )を組として選ぶSo$x_j > x _i $It is good as.

Therefore, find a pair of $ x _i, x _j $ that satisfies $ x \ _j-x _i = k (1 \ leqq x _i \ <x _j \ leqq N) $ with $ 1 \ leqq k \ leqq N-1 $. You can see that there is a $ Nk $ pair of $ (x \ _i, x _j) = (1,1 + k), (2,2 + k),… (Nk, N) $.

Also, for each $ x \ _i, x \ _j $, there are $ y \ _i and y \ _j $ in $ M $, so $ x \ _ j-x _i = k (1 \ leqq x _i \ <x There are $ (Nk) \ times M ^ 2 $ combinations of $ (x \ _ i, y \ _i) $ and $ (x \ _ j, y \ _j) $ that satisfy _j \ leqq N) $.

Therefore, anykAsk for this and add up,|y _i-y _j|In the case of, the solution can be obtained by calculating and adding them in the same calculation.

E.cc

//Include(Alphabetical order)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array

using namespace std;
typedef long long ll;

//macro
//for loop relationship
//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.
#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--)
//x is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
#define MAX(x) *max_element(ALL(x)) //Find the maximum value
#define MIN(x) *min_element(ALL(x)) //Find the minimum value
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 300000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#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;
}

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 of binomial coefficient
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,m,k;cin >> n >> m >> k;
    mint ans1=COM(n*m-2,k-2);
    mint ans1_=0;
    FOR(i,1,n-1)ans1_+=(i*m*m*(n-i));
    ans1*=ans1_;
    mint ans2=COM(n*m-2,k-2);
    mint ans2_=0;
    FOR(i,1,m-1)ans2_+=(i*n*n*(m-i));
    ans2*=ans2_;
    cout << ans1+ans2 << endl;
}

F problem

First, in the update queryg(x)=f(x)+|x-a|+bReplaced withThe absolute value part and the constant part are calculated independently, so they are calculated separately.I did it. Therefore, the part b is a simple addition, so in the followingOnly for the calculation of the absolute value partI will pay attention to it.

further,h(x)=|x-x_1|+|x-x_2|+…+|x-x_{n-1}|+|x-x_n|(x_1 \leqq x_2 \leqq … \leqq x_{n-1} \leqq x_n )Whenh(x)The smallest x that minimizesx_{[\frac{n+1}{2}]}Because it is a famous fact(If you look it up, it will come out, and it will come out in the past questions of AtCoder.), If you use thisO(1)It is possible to find the minimum value of x with. But it corresponds to xf(x)If you calculate the value ofO(Q)So I think about calculating this at high speed(At this rateO(Q^2))。

What you should remember here isSince it is difficult to calculate the absolute value as it is, consider removing itabout it. Here is the minimum valuexOnlyf(x)You just have to pay attention toxbelowx_iabout|x-x_i|=x-x_isoxMore thanx_iIt will be. Therefore,Become the smallestxbelow要素を保存する配列A_1とBecome the smallestxArray to store larger elementsA_2Prepare twois needed(If you do not prepare two, implementation is quite troublesomesoす。実装も工夫！).. Also, by thisO(1)sof(x)は計算soきますが、この計算about解説を省略するのso自分so確認してみてください。

Also, here it is necessary to insert $ O (\ log {n}) $ or $ O (1) $ into the sorted array, but in the case of a normal array it costs $ O (n) $. I will. Multiset can be used here. ** multiset can add, delete and search data for $ O (\ log {n}) $ respectively ** (The internal structure is a red-black tree, I used it for the first time this time).

Also, the element of $ A_1 $ must always be less than or equal to the element of $ A_2 $, and either $ len (A_1) = len (A_2) $ or $ len (A_1) = len (A_2) + 1 $ holds. , The last element of $ A_1 $ is minimized by $ x $ which minimizes $ f (x) $, $ len (A_1) to calculate $ f (x) $ by $ O (1) $ ), Len (A_2), sum (A_1), sum (A_2) $ should be prepared and these variables should be updated in the update query. there is. The implementation method is described in the comment out of the code below, so if you do not understand, please refer to that.

Furthermore, in the code below, there is a code to delete the first element and the last element of multiset, but if you specify the value of the element to be deleted, the element with the same value will be deleted at the same time, so ** Specify the range to delete need to do it**.

F.cc

//Include(Alphabetical order)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array

using namespace std;
typedef long long ll;

//macro
//for loop relationship
//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.
#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--)
//x is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
#define MAX(x) *max_element(ALL(x)) //Find the maximum value
#define MIN(x) *min_element(ALL(x)) //Find the minimum value
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair

//multiset Same guy deleted(If it's a normal erase)
//All you have to do is specify the range with the iterator
signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll q;cin >> q;
    multiset<ll> A1,A2;
    ll B=0;
    ll s1,s2;s1=0;s2=0;
    ll l1,l2;l1=0;l2=0;
    REP(i,q){
        ll x,a,b;cin >> x;
        if(x==1){
            cin >> a >> b;
            B+=b;
            if(i==0){
                A1.insert(a);
                l1+=1;
                s1+=a;
            //l1=At the time of l2
            //Check with l2 and put in l1 if it is the front
            //If not, put the minimum of l2 in l1
            //Put in A2 first and put the minimum in A1
            }else if((l1+l2)%2==0){
                s2+=a;
                A2.insert(a);
                ll j=*A2.begin();
                s1+=j;
                s2-=j;
                A1.insert(j);
                //A2.erase(j);
                A2.erase(A2.begin(),++A2.begin());
                l1+=1;
            //l1+1=At the time of l2
            //Check with l1 and put in l2 at the end
            //If not, put the maximum of l1 into l2
            //Put in A1 first and put the maximum in A2
            }else{
                s1+=a;
                A1.insert(a);
                ll j=*(--A1.end());
                s2+=j;
                s1-=j;
                A2.insert(j);
                A1.erase(--A1.end(),A1.end());
                l2+=1;
            }
        }else{
            ll j=*(--A1.end());
            cout << j << " " << -s1+s2+j*(l1-l2)+B << endl;
        }
    }
}