concours yukicoder 259 avis

résultat

スクリーンショット 2020-08-01 0.08.04.png

Impressions

R J'ai senti que le problème était difficile et je me suis enfui. Ce n'est pas difficile si vous suivez les bases, donc je le regrette. Dans le problème B, j'ai fait une erreur dans le temps constant et perdu. Je suis désolé ... Le problème C était une sorte de problème que je n'avais pas fait beaucoup, mais je l'ai résolu. Je suis content d'avoir été collant.

Problème A

(1) La plage de $ t $ dépend de $ D $, et $ D $ est ** extrêmement grande. ** Il est nécessaire de trouver la ** valeur minimale ** $ T $ de ce $ t $. (2) Cela vaut pour $ t <T $. Puisqu'il y a ** monotonie ** qui vaut pour $ t> T $, $ T $ peut être obtenu par dichotomie à cause de ces deux conditions. De plus, si la distance totale parcourue par chaque slime dans un certain $ t $ est calculée par $ O (N) $, le montant du calcul sera $ O (N \ log {D}) $, donc si vous pouvez écrire un programme à temps J'ai pensé.

Considérons maintenant la distance totale de déplacement de tous les slimes en $ t $, mais lorsque les deux slimes (vitesses sont $ v_1 $, $ v_2 $) sont combinés en un slime, la vitesse des slimes restants Le résultat est $ v_1 + v_2 $. Par conséquent, si vous * faites attention à la distance totale parcourue **, cela ne changera pas même si chaque slime ne fusionne pas, donc si vous considérez la distance parcourue par tous les slimes jusqu'à $ t $ (lorsqu'ils ne fusionnent pas), $ O Il peut être calculé par (N) $.

Veuillez également vous référer à cet article pour la dichotomie. De plus, ce problème peut être résolu avec $ O (N) $ au lieu de $ O (N \ log {D}) $ (Main Solution éditorial)).

A.py


n,d=map(int,input().split())
x=list(map(int,input().split()))
v=list(map(int,input().split()))
s=sum(v)

def f(k):
    return s*k

#c'est faux,r est vrai
l,r=0,1000000000000
while l+1<r:
    k=l+(r-l)//2
    if f(k)>=d:
        r=k
    else:
        l=k
print(r)

Problème B

Tout d'abord, vérifiez tous les nombres premiers qui peuvent être déterminés par le tamis Eratostenes ** car la requête est utilisée pour déterminer le nombre premier (cela rend la détermination de la requête première $ O (1) $). S'il est déterminé que $ p $ n'est pas un nombre premier, alors $ -1 $ doit être affiché, donc nous supposerons que $ p $ est un nombre premier et continuerons la discussion ci-dessous.

Sur cette base, si vous demandez simplement $ A ^ {P!} \ (Mod \ P) $ comme $ ((A ^ 1) ^ 2) ^ 3… $, il ne sera pas à temps même sous la condition de $ mod \ P $. Hmm. Ce qu'il faut retenir ici est le ** théorème de Fermat **. Je pense que vous devriez garder à l'esprit qu'il est de notoriété publique dans les problèmes liés à la puissance du $ surplus $. Dans ce théorème, ** $ A ^ {p-1} = 1 \ (mod \ p) $ ** vaut pour $ A $, qui n'est pas un multiple de $ p $ pour le nombre premier $ p $. Ici, $ A ^ {p!} = (A ^ {p-1}) ^ x \ (x = 1,2,…, p-2, p) $ tient, donc ($ \ car \ p $ est $ 2 $ ou plus qu'un nombre premier), $ A ^ {p!} = 0 \ (mod \ P) $ si $ A $ est un multiple de $ p $, $ A ^ {p!} = 1 \ sinon Il devient (mod \ P) $.

Pour résumer ce qui précède, $ -1 $ lorsque $ p $ n'est pas un nombre premier, $ 0 $ lorsque $ p $ est un nombre premier et $ A % p = 0 $, et $ A % p \ lorsque $ p $ est un nombre premier. Lorsque neq 0 $, $ 1 $ doit être affiché.

** J'ai oublié de changer la plage de «MAXRR» dans le code et j'ai émis WA **. C'était douloureux. Cela a pris beaucoup de temps.

B.cc


//Optimisation du compilateur
#pragma GCC optimize("Ofast")
//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 6000000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire

#define PN true //nombre premier
#define NPN false //Pas un nombre premier
//Non essentiel
#define MAXRR 3000 //√ Définissez un nombre supérieur ou égal à MAXR

//Supposons que les entiers jusqu'à MAXR soient des nombres premiers(Raser d'ici)
vector<bool> PN_chk(MAXR+1,PN);//0index correspond au i-ème entier i(0~MAXR)
//Préparer un tableau pour stocker les nombres premiers
vector<ll> PNs;

void se(){
    //0 et 1 ne sont pas des nombres premiers
    PN_chk[0]=NPN;PN_chk[1]=NPN;

    FOR(i,2,MAXRR){
        //Un nombre premier s'il est supposé être un nombre premier à votre arrivée
        if(PN_chk[i]) FOR(j,i,ll(MAXR/i)){PN_chk[j*i]=NPN;}
    }
    FOR(i,2,MAXR){
        if(PN_chk[i]) PNs.PB(i);
    }
}

ll modpow(ll a,ll n,ll p){
    if(n==0)return 1;
    ll t=modpow(a,n/2,p);
    t=t*t%p;
    if(n&1)t=t*a%p;
    return t;
}

signed main(){
    //Code pour accélérer la saisie
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    se();
    ll t;cin>>t;
    REP(_,t){
        ll a,p;cin>>a>>p;
        if(!PN_chk[p]){
            cout<<-1<<endl;
            continue;
        }
        if(a%p==0){
            cout<<0<<endl;
            continue;
        }
        cout<<1<<endl;
    }
}

Problème C

Si je connaissais le même sujet, je pourrais faire de mon mieux pour le mettre en œuvre, alors j'ai senti le pouvoir de la dévotion.

Premièrement, si vous mettez $ r_i et c_i $ comme indiqué ci-dessous, vous pouvez les diviser en quatre parties ci-dessous.

IMG_0509 2.JPG

Sur cette base, nous pouvons voir que la réponse à obtenir est d'obtenir le produit des produits des nombres contenus dans chacun des rectangles ①, ②, ③ et ④. Pour la partie incluse dans un tel rectangle, le traitement des requêtes peut être effectué avec $ O (1) $ en pré-calcul avec ** accumulation bidimensionnelle **.

Lors de la création d'une table par pré-calcul, ** dans le cas d'une somme cumulée bidimensionnelle ** est la suivante. De plus, chaque carré est $ a [x] [y] $, et les suivants sont tous indexés à 0.

$ s [x] [y]: = [0, x) × [0, y) La somme des sections rectangulaires de $ s[x+1][y+1] = s[x][y+1] + s[x+1][y] - s[x][y] + a[x][y]

Par conséquent, dans le cas du ** produit cumulatif bidimensionnel **, si cela se fait de la même manière, ce sera comme suit.

$ s [x] [y]: = [0, x) × [0, y) $ produit de sections rectangulaires s[x+1][y+1] = s[x][y+1] \times s[x+1][y] \div s[x][y] \times a[x][y]

Par conséquent, ce ** produit cumulatif bidimensionnel peut être défini dans quatre directions **, et les trois autres sections rectangulaires sont les suivantes. L'expression de l'intervalle est différente de la définition des mathématiques, mais j'espère que vous pouvez comprendre l'atmosphère. (J'essayais de le faire dans une atmosphère sans décrire ce qui suit. ** Je vais décrire en détail la politique **.)

$ s [x] [y]: = [w-1, x) × [0, y) $ produit de sections rectangulaires s[x-1][y+1] = s[x][y+1] \times s[x-1][y] \div s[x][y] \times a[x][y]

$ s [x] [y]: = [0, x) × [h-1, y) $ produit de sections rectangulaires s[x+1][y-1] = s[x][y-1] \times s[x+1][y] \div s[x][y] \times a[x][y]

$ s [x] [y]: = [w-1, x) × [h-1, y) $ produit de sections rectangulaires s[x+1][y+1] = s[x][y+1] \times s[x+1][y] \div s[x][y] \times a[x][y]

Si vous pouvez implémenter cela, vous pouvez écrire un programme en ** notant qu'il s'agit d'une section ouverte **. De plus, j'ai utilisé ma bibliothèque modint car je n'ai besoin de trouver que le reste divisé par 10 $ ^ 9 + 7 $.

Post-scriptum (8/2)

Diviser 0 en divisant la partie remplie du tout est gênant, il semble donc préférable de se rendre compte que ** le problème de trouver le produit de plusieurs nombres n'est exprimé que par le produit **.

C.cc


//Optimisation du compilateur
#pragma GCC optimize("Ofast")
//Inclure etc.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

//macro
//pour boucle
//L'argument est(Variables dans la boucle,Amplitude de mouvement)Ou(Variables dans la boucle,Premier numéro,Nombre d'extrémités)、のどちらOu
//Les variables de boucle sans D sont incrémentées de 1 et les variables de boucle avec D sont décrémentées de 1.
//FORA est une gamme de déclaration(Si c'est difficile à utiliser, effacez-le)
#define REP(i,n) for(ll i=0;i<ll(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=ll(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=ll(b);i--)
#define FORA(i,I) for(const auto& i:I)
//x est un conteneur tel que vector
#define ALL(x) x.begin(),x.end() 
#define SIZE(x) ll(x.size()) 
//constant
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie
//Abréviation
#define PB push_back //Insérer
#define MP make_pair //constructeur de paires
#define F first //Le premier élément de paire
#define S second //Le deuxième élément de paire

template<ll mod> class modint{
public:
    ll val=0;
    //constructeur
    modint(ll x=0){while(x<0)x+=mod;val=x%mod;}
    //Copier le constructeur
    modint(const modint &r){val=r.val;}
    //Opérateur arithmétique
    modint operator -(){return modint(-val);} //unaire
    modint operator +(const modint &r){return modint(*this)+=r;}
    modint operator -(const modint &r){return modint(*this)-=r;}
    modint operator *(const modint &r){return modint(*this)*=r;}
    modint operator /(const modint &r){return modint(*this)/=r;}
    //Opérateur d'assignation
    modint &operator +=(const modint &r){
        val+=r.val;
        if(val>=mod)val-=mod;
        return *this;
    }
    modint &operator -=(const modint &r){
        if(val<r.val)val+=mod;
        val-=r.val;
        return *this;
    }
    modint &operator *=(const modint &r){
        val=val*r.val%mod;
        return *this;
    }
    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
    bool operator ==(const modint& r){return this->val==r.val;}
    bool operator <(const modint& r){return this->val<r.val;}
    bool operator !=(const modint& r){return this->val!=r.val;}
};

using mint = modint<MOD>;

//Flux d'E / S
istream &operator >>(istream &is,mint& x){//N'ajoutez pas de const à x
    ll t;is >> t;
    x=t;
    return (is);
}
ostream &operator <<(ostream &os,const mint& x){
    return os<<x.val;
}

//Puissance
mint modpow(const mint &a,ll n){
    if(n==0)return 1;
    mint t=modpow(a,n/2);
    t=t*t;
    if(n&1)t=t*a;
    return t;
}



signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll h,w;cin>>h>>w;
    vector<vector<ll>> A(h,vector<ll>(w,0));
    REP(i,h)REP(j,w)cin>>A[i][j];
    vector<vector<vector<mint>>> s(4,vector<vector<mint>>(h+1,vector<mint>(w+1,1)));
    REP(j,h){
        REP(k,w){
            ll x,y;
            x=j;y=k;
            s[0][x+1][y+1]=s[0][x+1][y]*s[0][x][y+1]/s[0][x][y]*A[x][y];
        }
    }
    REP(j,h){
        REP(k,w-1){
            ll x,y;
            x=j;y=w-1-k;
            s[1][x+1][y-1]=s[1][x+1][y]*s[1][x][y-1]/s[1][x][y]*A[x][y];
        }
    }
    REP(j,h-1){
        REP(k,w){
            ll x,y;
            x=h-1-j;y=k;
            s[2][x-1][y+1]=s[2][x-1][y]*s[2][x][y+1]/s[2][x][y]*A[x][y];
        }
    }
    REP(j,h-1){
        REP(k,w-1){
            ll x,y;
            x=h-1-j;y=w-1-k;
            s[3][x-1][y-1]=s[3][x-1][y]*s[3][x][y-1]/s[3][x][y]*A[x][y];
        }
    }
    #if 0
    REP(i,4){
        REP(j,h){
            REP(k,w){
                cout<<s[i][j][k]<<" ";
            }
            cout<<endl;
        }
        cout<<endl;
    }
    #endif
    ll q;cin>>q;
    REP(_,q){
        ll r,c;cin>>r>>c;
        mint ans=1;
        ll x,y;
        x=r-1;y=c-1;
        ans*=s[0][x][y];
        //x=r;y=w-c;
        ans*=s[1][x][y];
        //x=h-r;y=c;
        ans*=s[2][x][y];
        //x=h-r;y=w-c;
        ans*=s[3][x][y];
        cout<<ans<<endl;
    }
}

Recommended Posts

concours yukicoder 259 avis
concours yukicoder 264 avis
concours yukicoder 261 avis
concours yukicoder 267 avis
concours yukicoder 266 avis
concours yukicoder 263 avis
yukicoder contest 268 avis
Critique du concours AtCoder Beginner Contest 152
AtCoder Grand Contest 041 Critique
yukicoder contest 265 Record de participation
Revue du concours régulier AtCoder 105
concours yukicoder 266 Record de participation
yukicoder contest 263 Record de participation
concours yukicoder 243 Record de participation
record de 256 entrées
yukicoder contest 273 Record de participation
Examen du concours de programmation Keyence 2020
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
concours yukicoder 252 Record de participation
concours yukicoder 259 Record de participation
Critique du concours AtCoder
concours yukicoder 249 Record de participation
AtCoder Débutant Contest 169 Évaluation
concours yukicoder 271 Record de participation
AtCoder Grand Contest 048 Critique
record de participation au concours 267 de yukicoder
Critique du concours AtCoder Débutant 181
Concours yukicoder 251 Record de participation
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
yukicoder contest 242 Record de participation
Critique du concours AtCoder Débutant 180
concours yukicoder 241 Record de participation
Critique du concours AtCoder pour débutant 177
record du concours 264 de yukicoder
AtCoder Débutant Contest 168 Critique
AtCoder Grand Contest 045 Critique
Revue du concours de programmation NOMURA 2020
AtCoder Grand Contest 044 Critique
yukicoder contest 245 record d'inscription
yukicoder contest 257 Record de participation
record de participation au concours yukicoder 250
Concours yukicoder 254 Record de participation
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
yukicoder contest 246 Record de participation
concours yukicoder 275 Record de participation
Concours yukicoder 274 Record de participation
Critique du concours AtCoder
concours yukicoder 247 Record de participation
AtCoder Grand Contest 046 Critique
AtCoder Débutant Contest 175 Critique
Examen du concours de programmation HHKB 2020
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156