[PYTHON] AtCoder Beginner Contest 156 Review

This time's results

スクリーンショット 2020-02-26 13.33.16.png

Impressions of this time

I felt that I was able to keep the performance in 4 digits and have the strength even though I didn't devote myself to the competition pro, but I can't go any further unless I devote myself more. I will do more devotion.

This time I was able to solve up to D, but it took a long time from the time I made the policy to the time I finished solving it. It was a pattern I had never seen for $ _nC_r $, so I found an article by Kencho-san and noticed it, but at first I was trying to find it by another TLE method, so I regret it.

When I solved E after the contest, it wasn't difficult if I thought about it calmly. What were you doing? Only about 2% of the brain can be used.

Problem A

Calculate by noting that the internal rating and the display rating are different.

A.py


n,r=map(int,input().split())
if n>=10:
    print(r)
else:
    print(r+100*(10-n))

B problem

Think about how many times you can divide by k by turning the while statement. It ends when n becomes 0.

B.py


ans=0
n,k=map(int,input().split())
while True:
    n=n//k
    ans+=1
    if n==0:
        break
print(ans)

C problem

Consider P from the smallest x-coordinate to the largest x-coordinate in order, and find the total sum of the minimum physical strengths.

C.py


n=int(input())
x=list(map(int,input().split()))
x.sort()
y=[]
for i in range(x[0],x[-1]+1):
    su=0
    for j in range(n):
        su+=((x[j]-i)**2)
    y.append(su)
print(min(y))

D problem

This issue is easy to think of in the policy itself. Because $_n C _1 + _n C _2 + … + _n C _{a-1} + _n C _{a+1} + … + _n C _{b-1} + _n C _{b+1} + … + _n C _n=2^n-1 - _n C _a - _n C _b$

This is because it is clear from the binomial theorem. However, since n is about 10 ^ 9 when calculating the combination, how to make a table for calculating the combination first (ABC042D ), ABC066D, ABC151E is O (n), so TLE It becomes. So, let's go back to the basics here. $ _N C _k = \ frac {n} {1} \ times \ frac {n-1} {2} \ times… \ times \ frac {n-k + 1} Since it is {k} , it is possible to perform calculations while always keeping the result as an int (divisible) by performing multiplication in order from the front, and it is possible to calculate with O (k). Also, I found it a little troublesome to think about the remainder of dividing by MOD ( = 10 ^ 9 + 7 $) at the time of this multiplication, so I used the modint library.

answerD.cc


#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cmath>
using namespace std;
typedef long long ll;

const ll MAX = 200000;
const ll MOD=1000000007;
//macro
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#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 INF 1000000000000
#define PB push_back
#define MP make_pair
#define F first
#define S second

template<ll mod> class modint{
public:
    ll val=0;
    //constructor
    constexpr modint(ll x=0):val(x%mod){while(x<0)x+=mod;}
    //Arithmetic operator
    constexpr modint operator +(const modint &r){return modint(*this)+=r;}
    constexpr modint operator -(const modint &r){return modint(*this)-=r;}
    constexpr modint operator *(const modint &r){return modint(*this)*=r;}
    constexpr modint operator /(const modint &r){return modint(*this)/=r;}
    //Assignment operator
    constexpr modint &operator +=(const modint &r){
        val+=r.val;
        if(val>=mod)val-=mod;
        return *this;
    }
    constexpr modint &operator -=(const modint &r){
        if(val<r.val)val+=mod;
        val-=r.val;
        return *this;
    }
    constexpr modint &operator *=(const modint &r){
        val=val*r.val%mod;
        return *this;
    }
    constexpr 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
    constexpr bool operator ==(const modint& r){return this->val==r.val;}
    constexpr bool operator <(const modint& r){return this->val<r.val;}
    constexpr bool operator !=(const modint& r){return this->val!=r.val;}
    //I / O stream
    friend constexpr istream &operator >>(istream &is,const modint<mod>& x){
        ll t;is >> t;
        x=modint<mod>(t);
        return (is);
    }
    friend constexpr ostream &operator <<(ostream &os,const modint<mod>& x){
        return os<<x.val;
    }
    //Exponentiation
    friend constexpr modint<mod> modpow(const modint<mod> &a,ll n){
        if(n==0)return 1;
        modint<mod> t=modpow(a,n/2);
        t=t*t;
        if(n&1)t=t*a;
        return t;
    }
};

using mint = modint<MOD>;

signed main(){
    ll n,a,b;cin >> n >> a >> b;
    const mint x=2;
    mint ans=modpow(x,n);
    ans-=1;
    vector<mint> com(b+1);
    FOR(i,1,b){
        if(i==1){
            com[i]=n;
        }else{
            com[i]=com[i-1];
            com[i]*=(n-i+1);
            com[i]/=i;
        }
    }
    ans=ans-com[a]-com[b];
    cout << ans << endl;
}

E problem

The contest was over if I had ** misunderstood ** that multiple people could move in one move ... I have to look at the sample properly ... Moreover, when I solved it again after the contest, I realized that it was not so difficult. First, when you ** pay attention to each room **, you can see that when there are no residents in that room, the people in that room have moved to another room. Therefore, when you move k times, you can think that there will be k rooms with 0 residents. Furthermore, at this time, the pattern that 0 to k-1 rooms become 0 people can also be expressed because ** just add extra movement ** (for details, [Explanation](https: //). Please refer to img.atcoder.jp/abc156/editorial.pdf).). Therefore, you can see that ** you should count each of the cases where there are 0 to k rooms for 0 people ** (however, note that k <= n-1). .. Also, when there are i rooms for 0 people, the way to choose a room for 0 people is $ _n C _i $ street, and there are 2 rooms with 1 or more people and the total number of people is n, so it is as follows. By thinking about, the combination of the number of people is $ _ {n-1} C _ {ni-1} $, and the combination of the number of people in the room when there are i rooms for 0 people is $ _n C _i \ times. It becomes _ {n-1} C _ {n-i-1} $.

IMG_0117.JPG

Therefore, if you write the program while paying attention to the fact that you want too much MOD ($ = 10 ^ 9 + 7 $), it will be as follows.

answerE.cc


#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<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
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#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 INF 1000000000000
#define MOD 1000000007
#define PB push_back
#define MP make_pair
#define F first
#define S second
const ll MAX = 200001;

ll fac[MAX], finv[MAX], inv[MAX];

//Pretreatment to make a table
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

//Binomial coefficient calculation
ll COM(ll n,ll k){
    if (n == 1) return 1;
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

signed main(){
    COMinit();
    ll n,k;cin >> n >> k;
    if(k>=n)k=n-1;
    ll ans=0;
    REP(i,k+1){
        ans+=(COM(n,i)*COM(n-1,n-i-1));
        ans%=MOD;
    }
    cout << ans << endl;
}

F problem

I don't think it's suitable for the level yet, so I'll skip it this time.

Recommended Posts

AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Beginner Contest 177
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder Beginner Contest 066 Review past questions
AtCoder Beginner Contest 181 Note
AtCoder Grand Contest 041 Review
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 182 Note
AtCoder Grand Contest 048 Review
AtCoder Beginner Contest 156 WriteUp
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
Solve AtCoder Beginner Contest 100-102
AtCoder Beginner Contest 167 Memorandum
AtCoder Beginner Contest 183 Note
AtCoder Beginner Contest 184 Note
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 188 Note
AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 110 Review of past questions
AtCoder Beginner Contest 117 Review of past questions
AtCoder Beginner Contest 070 Review of past questions
AtCoder Beginner Contest 105 Review of past questions
AtCoder Beginner Contest 112 Review of past questions