Critique du concours AtCoder pour débutant 156

Les résultats de cette fois

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

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} $.

IMG_0117.JPG

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.

Recommended Posts

Critique du concours AtCoder Beginner Contest 152
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
AtCoder Débutant Contest 169 Évaluation
Critique du concours AtCoder Débutant 181
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
Critique du concours AtCoder Débutant 180
Critique du concours AtCoder pour débutant 177
AtCoder Débutant Contest 168 Critique
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
Critique du concours AtCoder
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
AtCoder Débutant Contest 170 Critique
Critique du concours AtCoder
AtCoder Débutant Contest 173 Critique
AtCoder Débutant Contest 155 Critique
AtCoder Débutant Contest 162 Évaluation
Concours AtCoder Débutant 177
Concours AtCoder Débutant 179
Concours AtCoder Débutant 172
Concours AtCoder Débutant 180
Concours AtCoder Débutant 173
Concours Atcoder Débutant 153
AtCoder Beginner Contest 066 Revoir les questions précédentes
Concours AtCoder Débutant 181 Remarque
AtCoder Grand Contest 041 Critique
Revue du concours régulier AtCoder 105
Concours AtCoder Débutant 180 Remarque
Concours AtCoder Débutant 182 Remarque
AtCoder Grand Contest 048 Critique
Concours AtCoder pour débutants 156 WriteUp
AtCoder Grand Contest 045 Critique
AtCoder Grand Contest 044 Critique
Concours AtCoder pour débutants 167
Concours AtCoder Débutant 183 Remarque
Concours AtCoder Débutant 184 Remarque
Revue du concours régulier AtCoder 104
AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 072 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 127 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes