[PYTHON] AtCoder Beginner Contest 156 Review
This time's results
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
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}
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} $.
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