[PYTHON] Critique du concours AtCoder

Les résultats de cette fois

スクリーンショット 2020-09-20 12.14.47.png

Impressions de cette époque

Cette fois, ce fut également un résultat décevant. Je n'ai pas eu le temps de résoudre le problème F parce que j'avais tout le temps mis sur écoute le problème D. Si le problème F a un BIT (ou un arbre Seg), ce n'est pas si difficile, donc je pense que je l'ai résolu en environ 15 minutes.

Problème A

J'ai écrit les conditions de jugement à l'envers et j'ai passé du temps.

A.py


s=input()
if s[-1]!="s":
    print(s+"s")
else:
    print(s+"es")

Problème B

Vous devez simplement juger docilement s'ils sont égaux ou non. Faites attention uniquement aux références hors séquence.

B.py


n=int(input())
x,y=[],[]
for i in range(n):
    x_,y_=map(int,input().split())
    x.append(x_)
    y.append(y_)
for i in range(n-2):
    if x[i]==y[i] and x[i+1]==y[i+1] and x[i+2]==y[i+2]:
        print("Yes")
        break
else:
    print("No")

Problème C

$ A \ times B + C = N $, mais si vous décidez $ A, B $ tout en satisfaisant $ A \ times B <N $, ** $ C $ sera déterminé de manière unique **. Ici, comme $ 1 \ leqq A \ leqq N-1 $, le nombre ** pour $ B $ correspondant à ** $ A $ est calculé, mais lorsque $ N % A = 0 $, $ A \ $ B $ qui satisfait les temps B <N $ est $ B = 1,2,…, [\ frac {N} {A}] - 1 $ $ [\ frac {N} {A}] - 1 $ Donc, quand $ N % A \ neq 0 $, $ A \ times B <N $ est satisfait, $ B $ est $ B = 1,2,…, [\ frac {N} {A}] $ $ [\ frac {N} {A}] $ sera la rue. Par conséquent, il recherche tout et affiche le total.

C.py


n=int(input())
ans=0
for a in range(1,n):
    if n%a==0:
        ans+=(n//a-1)
    else:
        ans+=(n//a)
print(ans)

Problème D

J'ai l'impression d'avoir utilisé BIT dans le concours de production d'AtCoder pour la première fois. De plus, comme ce BIT peut ajouter des intervalles et que je ne l'ai pas implémenté, j'ai emprunté le BIT de kami. Fait. J'ai mis un modint dessus, je ne savais pas comment l'utiliser, et il était indexé en 1, donc je l'ai fait bogue pour toujours. ** Il est assez dangereux d'utiliser une bibliothèque que vous n'avez jamais utilisée ** ...

Tout d'abord, puisqu'il s'agit du nombre de méthodes de mouvement, considérons DP ** qui considère le mouvement comme une transition ($ dp [i]: = $ (nombre de méthodes de mouvement dans la masse $ i $) )). Cependant, cette fois, il y a des ** $ k $ sections **, donc si vous traitez chaque transition une par une, ce sera $ O (N ^ 2) $ et ce ne sera pas à temps. Ici, puisque $ k $ est de 10 au maximum, considérez ** bien gérer la transition pour chaque intervalle **. À ce stade, si l'intervalle est $ [l, r] $ et est dans la masse $ i $, alors $ dp [i + l] + = dp [i], dp [i + l + 1] + = dp [i] ],…, Dp [i + r] + = dp [i] $. Par conséquent, ** l'ajout de section doit être effectué de manière efficace et le BIT d'ajout de section doit être utilisé **.

Par conséquent, vous pouvez regarder $ i $ dans l'ordre croissant et ajouter à chacune des sections $ k $ dans l'ordre, et le montant du calcul sera $ O (Nk \ log {N}) $. De plus, puisque nous voulons trouver le reste de 998244353, nous devons mettre mod int dans BIT au lieu de long long ou int.

De plus, il semble y avoir une méthode de résolution avec $ O (NK) $ par la méthode imos, une méthode de réduction à un numéro de classe formel, et une méthode de résolution avec $ O (N \ log {N}) $ en utilisant un numéro de classe formel ( → article maspy) Mais je ne suis pas sûr, alors je vais sauter cette fois.

D.cc


//Options de débogage:-fsanitize=undefined,address

//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 998244353 //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

/* BIT:BIT compatible RAQ
La valeur initiale est un_1 = a_2 = ... = a_n = 0
· Ajouter(l,r,x): [l,r)Ajouter x à
· Somme(i): a_1 + a_2 + ... + a_Calculer i
Tous les calculs sont O(logn)
*/
template <typename T>
struct BIT {
    int n;             //Nombre d'éléments
    vector<T> bit[2];  //Emplacement de stockage des données
    BIT(int n_) { init(n_); }
    void init(int n_) {
        n = n_ + 1;
        for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
    }

    void add_sub(int p, int i, T x) {
        for (int idx = i; idx < n; idx += (idx & -idx)) {
            bit[p][idx] += x;
        }
    }
    void add(int l, int r, T x) {  // [l,r)Ajouter à
        add_sub(0, l, -x * (l - 1));
        add_sub(0, r, x * (r - 1));
        add_sub(1, l, x);
        add_sub(1, r, -x);
    }

    T sum_sub(int p, int i) {
        T s(0);
        for (int idx = i; idx > 0; idx -= (idx & -idx)) {
            s += bit[p][idx];
        }
        return s;
    }
    T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i ; }
};

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;
}


signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,k;cin>>n>>k;
    BIT<mint> dp(n);
    vector<pair<ll,ll>> sec(k);
    REP(i,k){
        ll l,r;cin>>l>>r;
        sec[i]=MP(l,r);
    }
    dp.add(1,2,1);
    REP(i,n){
        //cout<<i+1<<endl;
        REP(j,k){
            if(i+sec[j].F<=n){
                dp.add(i+sec[j].F+1,min(i+sec[j].S+2,n+1),dp.sum(i+1)-dp.sum(i));
                //cout<<i+1+sec[j].F<<" "<<min(i+1+sec[j].S+1,n+2)<<endl;
            }
        }
    }
    //cout<<1<<endl;
    cout<<dp.sum(n)-dp.sum(n-1)<<endl;
}

E problème

Je pense qu'il y avait un problème de compatibilité descendante l'autre jour.

$ A_ {i + 1} = A_ {i} ^ 2 \ mod \ m $ et $ A \ 1 = x $, et trouvez $ \ sum {i = 1} ^ nA_i $. Pour le moment, $ n $ vaut 10 $ ^ 9 $ au maximum, il n'est donc pas possible de trouver toutes les rues.

Ici, puisque chaque terme est le reste de $ m $, il n'y a que $ m $ rues au plus **, et quand $ (A \ _i = A \ _j) \ mod \ m $ tient, $ (A ) Puisque _ {i + 1} = A \ _ {j + 1}) \ mod \ m $ tient, une boucle d'une longueur maximale de $ m $ apparaît dans la ** séquence $ A $.

Par conséquent, si vous pouvez trouver cette boucle, vous pouvez effectuer le calcul à grande vitesse en considérant combien de fois la boucle apparaît de ** $ A \ _1 $ à $ A \ _n $ **. Je pense que si vous savez comment trouver une boucle, vous pouvez l'implémenter à grande vitesse, donc je vais vous montrer comment trouver une boucle ci-dessous.

① ** Trouvez $ A \ _i $ où le reste apparaît deux fois **

v ... Un tableau qui stocke dans l'ordre dans lequel le reste apparaît s ... réglé pour enregistrer le reste qui est sorti

Regardez $ A \ _1, A \ _2,… $ dans cet ordre et stockez-les dans v et s. À ce moment, si $ A \ _i $ avec la même valeur que stockée dans s apparaît, quittez ① avec cette valeur enregistrée.

② ** Séparez la boucle et l'avant de la boucle **

La valeur sauvegardée dans ① n'est pas incluse dans la boucle avant $ A \ _i $, qui apparaît pour la première fois. Par conséquent, il est séparé en cette partie (avant la boucle) et la partie après $ A \ _i $ (boucle).

Si $ A \ _n $ est avant la boucle, l'opération se termine à ce point et la sortie est effectuée. Si $ A \ _n $ est inclus dans la boucle, calculez avant la boucle, mettez à jour $ n $ avec le nombre de termes restant, mettez à jour v pour être une boucle uniquement, après avoir fait trois choses Passez à ③.

③ ** Calculez la boucle **

Vous pouvez demander les informations suivantes après ②. l… longueur de la boucle n… La longueur de la séquence restante $ [\ frac {n} {l}] … Combien de fois la boucle apparaît `n% l`… Combien la boucle ne tourne pas `s`… Somme dans la boucle ( O (l) $) t… La somme des parties qui ne font pas le tour de la boucle

Calculez la boucle séparée en (2). Les informations ci-dessus sont faciles à trouver, donc la réponse est $ [\ frac {n} {l}] \ times s + t $.

E.py


n,x,m=map(int,input().split())
cand=[x]
cands=set()
cands.add(x)
for i in range(m):
    c=(cand[-1]**2)%m
    if c in cands:
        break
    else:
        cand.append(c)
        cands.add(c)
#Le début de la boucle
#print(cand)
p=cand.index(c)
if x<p:
    print(sum(cand[:x]))
    exit()
ans=sum(cand[:p])
cand=cand[p:]
#print(ans)
n-=p
#Nombre de boucles
tim=n//len(cand)
ama=n%len(cand)
ans+=tim*sum(cand)
ans+=sum(cand[:ama])
print(ans)
#print(p)
#print(cand)

Problème F

Il peut être résolu en utilisant l'addition d'intervalle BIT après C. Dans ce qui suit, j'ai essayé d'expliquer avec des mots autant que possible, mais il y a des parties que je n'ai pas été en mesure de transmettre, donc je pense que vous approfondirez votre compréhension en ** dessinant un diagramme et en expérimentant **.

Quand je l'ai vu pour la première fois, je l'ai mal lu et j'ai oublié les informations ** les plus proches **. Ici, si nous considérons le problème à l'aide d'un diagramme, ce sera comme suit.

IMG_0637.PNG

En supposant que les opérations sont effectuées dans l'ordre des nombres encerclés, la partie indiquée par la flèche peut être peinte en blanc. À ce stade, en faisant attention à (1), par exemple, le nombre de cellules qui peuvent être peintes lorsque chaque ligne est sélectionnée est petit. De même, si vous faites attention à ②, vous pouvez réduire le nombre de carrés pouvant être peints lorsque chaque colonne est sélectionnée. De plus, en ce qui concerne (4), puisqu'il n'est pas possible de réduire le nombre de cellules de (2), toute cellule noire de cette colonne peut être rendue blanche. En d'autres termes, lorsque vous sélectionnez une ligne (ou une colonne), vous pouvez voir qu'il existe des opérations qui modifient le nombre de cellules qui peuvent changer la couleur d'une colonne (ou ligne) et des opérations qui ne changent pas **.

Maintenant, après plus d'expérimentation, je vais enregistrer la colonne la plus à gauche ($ r ) et la ligne supérieure ( d $) sélectionnées jusqu'à présent ** et la mettre à jour. Si vous le faites, vous pouvez le considérer comme une opération pour changer le nombre de cellules ** (la valeur initiale est $ r = c = n $). Par exemple, si vous sélectionnez $ c $ qui satisfait $ c <r $ et effectuez l'opération, alors lorsque vous sélectionnez la 2e à $ d $ -1er ligne, le nombre de cellules dont la couleur peut être modifiée est à l'origine $ r. Ce qui était de -2 $ est réduit à $ c-2 $. Par conséquent, en plus de $ r et d $, $ row et column $ ** sont également préparés, qui stockent l'index de la cellule blanche avec le plus petit index lorsque la ligne ** $ i $ et la colonne $ i $ sont sélectionnées. Je vais. De plus, ces éléments nécessitent une mise à jour d'intervalle, ils sont donc désignés comme BIT. Bien sûr, une structure de données telle que SegmentTreeBeats qui peut mettre à jour la section de ** min peut être utilisée, mais ** le nombre de cellules dont la couleur peut être modifiée est le même avant et après le changement de la section sélectionnée (✳︎) ** Par conséquent, il peut être traité par ajout de section.

(✳︎)… Si vous pensez dans la figure, si vous avez sélectionné $ (d, 1) $ dans ①, tout élément de $ row $ sera remplacé de $ n $ à $ d $. Autrement dit, ajoutez simplement $ d-n $ à n'importe quel élément. La même chose peut être dite pour toute opération.

F.cc


//Options de débogage:-fsanitize=undefined,address

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

/* BIT:BIT compatible RAQ
La valeur initiale est un_1 = a_2 = ... = a_n = 0
· Ajouter(l,r,x): [l,r)Ajouter x à
· Somme(i): a_1 + a_2 + ... + a_Calculer i
Tous les calculs sont O(logn)
*/
template <typename T>
struct BIT {
    int n;             //Nombre d'éléments
    vector<T> bit[2];  //Emplacement de stockage des données
    BIT(int n_) { init(n_); }
    void init(int n_) {
        n = n_ + 1;
        for (int p = 0; p < 2; p++) bit[p].assign(n, 0);
    }

    void add_sub(int p, int i, T x) {
        for (int idx = i; idx < n; idx += (idx & -idx)) {
            bit[p][idx] += x;
        }
    }
    void add(int l, int r, T x) {  // [l,r)Ajouter à
        add_sub(0, l, -x * (l - 1));
        add_sub(0, r, x * (r - 1));
        add_sub(1, l, x);
        add_sub(1, r, -x);
    }

    T sum_sub(int p, int i) {
        T s(0);
        for (int idx = i; idx > 0; idx -= (idx & -idx)) {
            s += bit[p][idx];
        }
        return s;
    }
    T sum(int i) { return sum_sub(0, i) + sum_sub(1, i) * i ; }
};


signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,q;cin>>n>>q;
    BIT<ll> row(n);
    row.add(1,n+1,n);
    BIT<ll> column(n);
    column.add(1,n+1,n);
    ll d,r;d=n;r=n;
    ll ans=0;
    REP(_,q){
        ll x,y;cin>>x>>y;
        if(x==1){
            ans+=column.sum(y)-column.sum(y-1)-2;
            //cout<<column.sum(y)-column.sum(y-1)-1<<endl;
            if(y<r){
                row.add(1,d,(y-row.sum(1)));
                r=y;
            }
        }else{
            ans+=row.sum(y)-row.sum(y-1)-2;
            //cout<<row.sum(y)-row.sum(y-1)-1<<endl;
            if(y<d){
                column.add(1,r,(y-column.sum(1)));
                d=y;
            }
        }
    }
    cout<<(n-2)*(n-2)-ans<<endl;
}

Recommended Posts

Critique du concours AtCoder pour débutant 166
AtCoder Débutant Contest 167 Évaluation
Critique du concours AtCoder
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
AtCoder Débutant Contest 175 Critique
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 179
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 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
AtCoder Regular Contest 106 Évaluation
Concours AtCoder Débutant 184 Remarque
AtCoder Grand Contest 046 Critique
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 113 Revue des questions précédentes
AtCoder Beginner Contest 074 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 054 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