[PYTHON] Critique du concours AtCoder pour débutant 156

Les résultats de cette fois

Impressions de cette époque

J'ai senti que j'étais capable de garder la performance à 4 chiffres et d'avoir la force même si je ne me consacrais pas à la compétition, mais je ne peux pas aller plus loin si je ne me consacre plus. Je ferai plus de dévotion.

Cette fois, j'ai pu résoudre jusqu'à D, mais il a fallu beaucoup de temps entre le moment où j'ai élaboré la politique et le moment où j'ai fini de la résoudre. C'était un modèle que je n'avais jamais vu pour $ _nC_r $, donc j'ai trouvé un article de Kencho-san et je l'ai remarqué, mais au début j'essayais de le trouver par une autre méthode TLE, donc je le regrette.

Quand j'ai résolu E après le concours, ce n'était pas difficile si j'y pensais calmement. Que faisiez-vous? Seulement environ 2% du cerveau peut être utilisé.

Problème A

Notez que le classement interne et le classement d'affichage sont différents.

A.py

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

Problème B

Pensez au nombre de fois que vous pouvez diviser par k en tournant l'instruction while. Il se termine lorsque n devient 0.

B.py

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

Problème C

Considérez P de la plus petite coordonnée x à la plus grande coordonnée x dans l'ordre, et trouvez la somme totale de la force physique minimale parmi elles.

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))

Problème D

Cette question est facile à penser dans la politique elle-même. Parce que $_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$

C'est parce que cela ressort clairement du théorème binomial. Cependant, comme n vaut environ 10 ^ 9 lors du calcul de la combinaison, comment créer d'abord un tableau pour calculer la combinaison (ABC042D ), ABC066D, ABC151E est O (n), donc TLE Ce sera. Revenons donc à l'essentiel ici. $ _N C _k = \ frac {n} {1} \ times \ frac {n-1} {2} \ times… \ times \ frac {n-k + 1} Puisqu'il est {k} , il est possible d'effectuer le calcul en gardant toujours le résultat en int (divisible) en effectuant la multiplication dans l'ordre à partir du front, et il est possible de l'obtenir par O (k). De plus, j'ai senti qu'il était un peu gênant de penser au reste de la division par MOD ( = 10 ^ 9 + 7 $) au moment de cette multiplication, j'ai donc utilisé la bibliothèque modint.

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() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à 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;
    //constructeur
    constexpr modint(ll x=0):val(x%mod){while(x<0)x+=mod;}
    //Opérateur arithmétique
    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;}
    //Opérateur d'assignation
    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;
    }
    //Opérateur de comparaison d'équivalence
    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;}
    //Flux d'E / S
    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;
    }
    //Puissance
    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 problème

Le concours était terminé si j'avais ** mal compris ** que plusieurs personnes pouvaient déménager en un seul mouvement ... Je dois bien regarder l'échantillon ... De plus, quand je l'ai résolu à nouveau après le concours, j'ai réalisé que ce n'était pas si difficile. Premièrement, lorsque vous ** faites attention à chaque pièce **, vous pouvez voir que lorsqu'il n'y a aucun résident dans cette pièce, les personnes dans cette pièce ont déménagé dans une autre pièce. Par conséquent, lorsque vous déménagez k fois, vous pouvez penser qu'il y aura k chambres avec 0 résidents. De plus, à ce moment, le modèle dans lequel 0 à k-1 pièces deviennent 0 personnes peut également être exprimé parce que c'est ** juste pour ajouter du mouvement supplémentaire ** (pour plus de détails, [Explication](https: //). Veuillez vous référer à img.atcoder.jp/abc156/editorial.pdf).). Par conséquent, vous pouvez voir que vous devez compter chacun des cas où il y a 0 à k chambres pour ** 0 personnes ** (notez cependant que k <= n-1). .. De plus, quand il y a i chambres pour 0 personnes, la façon de choisir une chambre pour 0 personnes est $ _n C _i $ rue, et il y a 2 chambres avec 1 personne ou plus et le nombre total de personnes est n, comme suit En y réfléchissant, la combinaison du nombre de personnes est $ _ {n-1} C _ {ni-1} $, et la combinaison du nombre de personnes dans la salle quand il y a i chambres pour 0 personne est $ _n C _i \ fois Il devient _ {n-1} C _ {n-i-1} $.

Par conséquent, si vous écrivez le programme en faisant attention à la quantité excessive de MOD ($ = 10 ^ 9 + 7 $), ce sera comme suit.

answerE.cc

#include<algorithm>//sort,Recherche de bisection,Tel
#include<bitset>//Jeu de bits de longueur fixe
#include<cmath>//pow,journal etc.
#include<complex>//Nombre complexe
#include<deque>//File d'attente d'accès double
#include<functional>//trier plus
#include<iomanip>//setprecision(Erreur de sortie en virgule flottante)
#include<iostream>//Entrée sortie
#include<map>//map(dictionnaire)
#include<numeric>//iota(Génération d'une chaîne entière),pgcd et lcm(c++17)
#include<queue>//queue
#include<set>//ensemble
#include<stack>//empiler
#include<string>//Chaîne
#include<unordered_map>//Carte avec itérateur mais sans ordre
#include<unordered_set>//Il y a un itérateur mais l'ordre n'est pas maintenu défini
#include<utility>//pair
#include<vector>//Tableau de longueur variable

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() //Je souhaite omettre des arguments tels que le tri
#define SIZE(x) ((ll)(x).size()) //taille à la taille_Changement de t à 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];

//Prétraitement pour faire une 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;
    }
}

//Calcul du coefficient binaire
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;
}

Problème F

Je ne pense pas que ce soit encore adapté au niveau, je vais donc l'ignorer cette fois.