[PYTHON] AtCoder Anfängerwettbewerb 156 Bewertung

Die Ergebnisse dieser Zeit

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

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

IMG_0117.JPG

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.

Recommended Posts

AtCoder Anfängerwettbewerb 152 Rückblick
AtCoder Beginner Contest 160 Bewertung
AtCoder Anfängerwettbewerb 178 Bewertung
AtCoder Anfängerwettbewerb 166 Bewertung
AtCoder Anfängerwettbewerb 167 Bewertung
AtCoder Beginner Contest 169 Bewertung
AtCoder Beginner Contest 181 Bewertung
AtCoder Beginner Contest 171 Bewertung
AtCoder Beginner Contest 182 Bewertung
AtCoder Beginner Contest 180 Bewertung
AtCoder Anfängerwettbewerb 177 Rückblick
AtCoder Anfängerwettbewerb 168 Bewertung
AtCoder Beginner Contest 179 Bewertung
AtCoder Beginner Contest 172 Bewertung
AtCoder Anfängerwettbewerb 176 Bewertung
AtCoder Anfängerwettbewerb 174 Bewertung
AtCoder Beginner Contest 153 Bewertung
AtCoder Anfängerwettbewerb 156 Bewertung
AtCoder Beginner Contest 161 Bewertung
AtCoder Beginner Contest 170 Bewertung
AtCoder Beginner Contest 165 Bewertung
AtCoder Beginner Contest 173 Bewertung
AtCoder Anfängerwettbewerb 155 Bewertung
AtCoder Beginner Contest 162 Bewertung
AtCoder Anfängerwettbewerb 177
AtCoder Anfängerwettbewerb 179
AtCoder Anfängerwettbewerb 172
AtCoder Anfängerwettbewerb 180
AtCoder Anfängerwettbewerb 173
Atcoder Anfänger Wettbewerb 153
AtCoder Beginner Contest 066 Überprüfen Sie frühere Fragen
AtCoder Anfängerwettbewerb 181 Hinweis
AtCoder Grand Contest 041 Bewertung
AtCoder Regular Contest 105 Bewertung
AtCoder Anfängerwettbewerb 180 Hinweis
AtCoder Anfängerwettbewerb 182 Hinweis
AtCoder Grand Contest 048 Bewertung
AtCoder Anfängerwettbewerb 156 WriteUp
AtCoder Grand Contest 045 Bewertung
AtCoder Grand Contest 044 Bewertung
AtCoder Beginner Contest 167 Memorandum
AtCoder Anfängerwettbewerb 183 Hinweis
AtCoder Anfängerwettbewerb 184 Hinweis
AtCoder Regular Contest 104 Bewertung
AtCoder Beginner Contest 102 Rückblick auf frühere Fragen
AtCoder Beginner Contest 072 Rückblick auf frühere Fragen
AtCoder Beginner Contest 085 Rückblick auf frühere Fragen
AtCoder Beginner Contest 062 Rückblick auf frühere Fragen
AtCoder Beginner Contest 051 Rückblick auf frühere Fragen
AtCoder Beginner Contest 127 Rückblick auf frühere Fragen
AtCoder Beginner Contest 119 Rückblick auf frühere Fragen
AtCoder Beginner Contest 151 Rückblick auf frühere Fragen
AtCoder Beginner Contest 075 Rückblick auf frühere Fragen
AtCoder Beginner Contest 110 Rückblick auf frühere Fragen
AtCoder Beginner Contest 117 Rückblick auf frühere Fragen
AtCoder Beginner Contest 070 Rückblick auf frühere Fragen
AtCoder Beginner Contest 105 Rückblick auf frühere Fragen
AtCoder Beginner Contest 112 Rückblick auf frühere Fragen