[PYTHON] AtCoder Anfängerwettbewerb 156 Bewertung

Die Ergebnisse dieser Zeit

Eindrücke dieser Zeit

Obwohl ich mich nicht dem Wettbewerb gewidmet habe, hatte ich das Gefühl, dass ich die Leistung im 4-stelligen Bereich halten konnte und die Kraft hatte, aber ich kann nicht weiter gehen, ohne mich selbst zu widmen. Ich werde mehr Hingabe tun.

Dieses Mal konnte ich bis zu D lösen, aber es dauerte lange von der Erstellung der Richtlinie bis zur Fertigstellung. Es war ein Muster, das ich für $ _nC_r $ noch nie gesehen hatte, also fand ich einen Artikel von Kencho-san und bemerkte es, aber zuerst versuchte ich es mit einer anderen TLE-Methode zu finden, also bereue ich es.

Als ich E nach dem Wettbewerb löste, war es nicht schwierig, wenn ich ruhig darüber nachdachte. Was hast du gemacht? Nur etwa 2% des Gehirns können verwendet werden.

Problem A

Beachten Sie, dass die interne Bewertung und die Anzeigebewertung unterschiedlich sind.

A.py

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

B-Problem

Überlegen Sie, wie oft Sie durch k teilen können, indem Sie die while-Anweisung drehen. Es endet, wenn n 0 wird.

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

Betrachten Sie P von der kleinsten x-Koordinate zur größten x-Koordinate in der Reihenfolge und ermitteln Sie die Gesamtsumme der minimalen physikalischen Stärke unter ihnen.

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

Dieses Problem ist in der Richtlinie selbst leicht zu erkennen. weil $_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$

Dies liegt daran, dass dies aus dem Binomialsatz hervorgeht. Da n bei der Berechnung der Kombination etwa 10 ^ 9 beträgt, wird zunächst eine Tabelle zur Berechnung der Kombination erstellt (ABC042D. ), ABC066D, ABC151E usw. Es wird sein. Kehren wir hier zu den Grundlagen zurück. $ _N C _k = \ frac {n} {1} \ times \ frac {n-1} {2} \ times… \ times \ frac {n-k + 1} Da es {k} $ ist, ist es möglich, Berechnungen durchzuführen, während das Ergebnis immer in int (teilbar) bleibt, indem eine Multiplikation in der Reihenfolge von vorne durchgeführt wird, und es ist möglich, es mit O (k) zu erhalten. Außerdem fand ich es etwas mühsam, über den Rest der Division durch MOD ($ = 10 ^ 9 + 7 $) zum Zeitpunkt dieser Multiplikation nachzudenken, also habe ich die Modint-Bibliothek verwendet.

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;
//Makro
#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() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach 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;
    //Konstrukteur
    constexpr modint(ll x=0):val(x%mod){while(x<0)x+=mod;}
    //Arithmetischer 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;}
    //Aufgabenverwalter
    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;
    }
    //Äquivalenzvergleichsoperator
    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;}
    //E / A-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;
    }
    //Leistung
    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

Der Wettbewerb war vorbei, wenn ich ** missverstanden ** hatte, dass sich mehrere Personen in einem Zug bewegen könnten ... Ich muss mir das Beispiel richtig ansehen ... Als ich es nach dem Wettbewerb wieder löste, wurde mir klar, dass es nicht so schwierig war. Wenn Sie ** auf jeden Raum achten **, können Sie zunächst feststellen, dass die Personen in diesem Raum in einen anderen Raum gezogen sind, wenn sich keine Bewohner in diesem Raum befinden. Wenn Sie sich also k-mal bewegen, können Sie davon ausgehen, dass es k Zimmer mit 0 Bewohnern gibt. Darüber hinaus kann zu diesem Zeitpunkt auch das Muster ausgedrückt werden, in dem 0 bis k-1 Räume zu 0 Personen werden, da dies nur dazu dient, zusätzliche Bewegung hinzuzufügen (Einzelheiten siehe [Erläuterung](https: //). Bitte beziehen Sie sich auf img.atcoder.jp/abc156/editorial.pdf).). Daher können Sie sehen, dass Sie jeden Fall zählen sollten, in dem 0 bis k Räume für ** 0 Personen ** vorhanden sind (beachten Sie jedoch, dass k <= n-1 ist). .. Wenn es i Räume für 0 Personen gibt, ist die Möglichkeit, einen Raum für 0 Personen auszuwählen, $ _n C _i $ street, und es gibt 2 Räume mit 1 oder mehr Personen und die Gesamtzahl der Personen ist n, also wie folgt Wenn man darüber nachdenkt, ist die Kombination der Anzahl der Personen $ _ {n-1} C _ {ni-1} $, und die Kombination der Anzahl der Personen im Raum, wenn es i Räume für 0 Personen gibt, ist $ _n C _i \ mal Es wird _ {n-1} C _ {n-i-1} $.

Wenn Sie das Programm schreiben, während Sie auf die übermäßige Menge an MOD ($ = 10 ^ 9 + 7 $) achten, ist dies wie folgt.

answerE.cc

#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge

using namespace std;
typedef long long ll;

//Makro
#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() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach 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];

//Vorbehandlung, um einen Tisch zu machen
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;
    }
}

//Berechnung des Binärkoeffizienten
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

Ich denke, es ist noch nicht für das Level geeignet, also werde ich es dieses Mal überspringen.