[PYTHON] AtCoder Beginner Contest 127 Revue des questions précédentes

Les résultats de cette fois

Impressions de cette époque

J'avais la bonne idée pour le problème E et le problème F, mais je ne pouvais pas le faire AC parce que je ne pouvais pas terminer l'examen et la mise en œuvre. Étant donné que le problème D peut être résolu rapidement, j'essaie de ** considérer et mettre en œuvre attentivement **. De plus, bien que l'implémentation ait été gênante pour le problème F, elle n'est pas si difficile à implémenter, alors n'oubliez pas ** Considération dans la section implémentation **.

Problème A

Faites simplement l'affaire avec soin.

A.py

a,b=map(int,input().split())
if a>=13:
    print(b)
elif a>=6:
    print(b//2)
else:
    print(0)

Problème B

Notez chaque section tour à tour.

B.py

r,d,x=map(int,input().split())
ans=[x]
for i in range(10):
    ans.append(r*ans[-1]-d)
for i in range(1,11):
    print(ans[i])

Problème C

Seule la i-ème carte d'identité qui satisfait $ max (L) \ leqq i \ leqq min (R) $ peut traverser toutes les portes avec une seule carte.

Cela peut être prouvé comme suit. Quand $ i \ <max (L) $, $ L_j = max (L) $ ne peut pas être passé par la jième porte, et quand $ i > min (R) $, $ L_j = max ( R) Impossible de passer par la jème porte, qui est $. Aussi, quand il s'agit de $ max (L) \ leqq i \ leqq max (R) $, il est clair que la i-ième carte peut être utilisée pour toutes les portes. De ce qui précède, j'ai pu le prouver.

C.py

n,m=map(int,input().split())
l,r=[],[]
for i in range(m):
    x,y=map(int,input().split())
    l.append(x)
    r.append(y)
ansl,ansr=max(l),min(r)
print(max(0,ansr-ansl+1))

Problème D

Puisqu'il est devenu possible de répondre immédiatement jusqu'au diff vert, je voudrais me consacrer pour que je puisse répondre immédiatement depuis le diff d'eau.

Si vous sélectionnez une carte et répétez la réécriture, elle deviendra O (MN) et elle ne sera évidemment pas à temps, alors considérez une autre méthode.

Ici, j'ai l'impression que ** je veux augmenter le nombre de chaque carte autant que possible **. De plus, chaque carte peut être réécrite pour prendre n'importe quel nombre de $ C_1, C_2,…, C_M $, alors ** sélectionnez le plus grand nombre $ N $ parmi tous les nombres possibles ** J'ai décidé de prendre la politique.

De plus, si vous enregistrez ** tous les nombres possibles ($ A_1,… A_N, C_1,…, C_M $) comme type de dict **, vous pouvez facilement calculer en sélectionnant $ N $ dans l'ordre décroissant. peut faire.

answerD.py

from collections import Counter
n,m=map(int,input().split())
d=Counter(list(map(int,input().split())))
for i in range(m):
    b,c=map(int,input().split())
    if c in d:
        d[c]+=b
    else:
        d[c]=b
d=sorted(Counter(d).items(),reverse=True)
check=n
ans=0
for i in d:
    if i[1]<check:
        check-=i[1]
        ans+=(i[0]*i[1])
    else:
        ans+=(i[0]*check)
        print(ans)
        break

E problème

Dans un tel problème (calculer la somme de ** 〇〇, compter le nombre de motifs de 〇〇, etc. **), il ne suffit pas de compter tous les motifs, donc ** vous pouvez compter les mêmes motifs ensemble. **. Je devrais être en mesure de le résoudre conformément à cette politique, mais je ne pouvais pas le faire, quel que soit le nombre de fois que j'ai essayé ce comptage. (← ** La cause est la politesse de la considération **. Il faut bien l'organiser lors de la prise de notes.)

Premier,|x_i-x_j|+|y_i-y_j|Est déterminé par les carrés des deux pièces, Il y a deux carrésKLe motif sélectionné parmi les carrés des pièces individuelles est celui des carrés excluant ces deux carrés.(N \times M-2)DeK-2En pensant à choisir le carré de la pièce,$ _{n \times m-2} C _{k-2}$Ce sera dans la rue.

Aussi, comment choisir les deux pièces auxquelles faire attention$ _{n \times m} C _2 Si vous gardez cela dans la rue, le montant du calcul seraO(n \times m)Ce ne sera pas à temps, nous devons donc créer plus de modèles. Ce que je veux savoir ici**|x _i-x _j|+|y _i-y _j|La valeur du**alors**|x _i-x _j|Quand|y _i-y _j|$の計算は独立にalorsきる**こQuandを考慮すれば、それぞれLa valeur duのパターンを別々alors計算しても良いこQuandがわかります。

(Ci-dessous, pour plus de simplicité|x _i-x _j|Je ne pense qu'au moment de|y _i-y _j|La même chose est vraie au moment de.)

Donc,|x _i -x _j |=kQuandkCorrespond à la valeur de(x _i,x _j )Pensez à savoir combien il y a de paires. ici,1 \leqq x _i ,x _j \leqq NEst$ x _i,x _j Peut être différent(\because x _i =x _j $Au moment de k=Puisqu'il vaut 0, cela n'affecte pas le total)Alors1 \leqq k \leqq N-1Ce sera. Aussi, à ce moment(x _i,x _j )を組として選ぶAlors$x_j > x _i $C'est bon comme ça.

Par conséquent, trouvez une paire de $ x _i, x _j $ qui satisfait $ x \ _j-x _i = k (1 \ leqq x _i \ <x _j \ leqq N) $ avec $ 1 \ leqq k \ leqq N-1 $ Vous pouvez voir qu'il y a $ Nk $ paires de $ (x \ _i, x _j) = (1,1 + k), (2,2 + k),… (Nk, N) $.

Aussi, pour chaque $ x \ _i, x \ _j $, il y a $ y \ _i et y \ _j $ dans $ M $, donc $ x \ _j-x _i = k (1 \ leqq x _i \ <x) Il y a $ (Nk) \ times M ^ 2 $ combinaisons de $ (x \ _i, y \ _i) $ et $ (x \ _ j, y \ _j) $ qui satisfont _j \ leqq N) $.

Par conséquent, toutkDemandez ceci et additionnez,|y _i-y _j|Dans le cas de, la solution peut être obtenue en calculant et en additionnant par le même calcul.

E.cc

//Comprendre(Ordre alphabétique)
#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<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#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
//pour la relation de 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.
#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--)
//x est un conteneur tel que vector
#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 MAX(x) *max_element(ALL(x)) //Trouvez la valeur maximale
#define MIN(x) *min_element(ALL(x)) //Trouvez la valeur minimale
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 300000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#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;
}

mint fac[MAXR+1],finv[MAXR+1],inv[MAXR+1];

//Créer une table
void COMinit() {
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    FOR(i,2,MAXR){
        fac[i]=fac[i-1]*mint(i);
        inv[i]=-inv[MOD%i]*mint(MOD/i);
        finv[i]=finv[i-1]*inv[i];
    }
}

//Calcul du coefficient binomial
mint COM(ll n,ll k){
    if(n<k)return 0;
    if(n<0 || k<0)return 0;
    return fac[n]*finv[k]*finv[n-k];
}

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    COMinit();
    ll n,m,k;cin >> n >> m >> k;
    mint ans1=COM(n*m-2,k-2);
    mint ans1_=0;
    FOR(i,1,n-1)ans1_+=(i*m*m*(n-i));
    ans1*=ans1_;
    mint ans2=COM(n*m-2,k-2);
    mint ans2_=0;
    FOR(i,1,m-1)ans2_+=(i*n*n*(m-i));
    ans2*=ans2_;
    cout << ans1+ans2 << endl;
}

F problem

Tout d'abord, dans la requête de mise à jourg(x)=f(x)+|x-a|+bRemplacé parÉtant donné que le calcul de la partie valeur absolue et de la partie valeur constante sont indépendants, ils sont calculés séparément.Je l'ai fait. Par conséquent, la partie b est un simple ajout, donc dans ce qui suitUniquement pour le calcul de la partie valeur absolueJ'y prêterai attention.

plus loin,h(x)=|x-x_1|+|x-x_2|+…+|x-x_{n-1}|+|x-x_n|(x_1 \leqq x_2 \leqq … \leqq x_{n-1} \leqq x_n )Quandh(x)Le plus petit x qui minimisex_{[\frac{n+1}{2}]}Est un fait célèbre(Si vous le recherchez, il sortira, et il sortira dans les précédentes questions d'AtCoder.), Si vous utilisez ceO(1)Il est possible de trouver la valeur minimale de x avec. Mais cela correspond à xf(x)Si vous calculez la valeur deO(Q)Alors je pense à calculer ça à grande vitesse(À ce niveau làO(Q^2))。

Ce que vous devez retenir ici estComme il est difficile de calculer la valeur absolue telle quelle, envisagez de la supprimerà propos de ça. Voici la valeur minimalexSeulementf(x)Vous devez juste faire attention àxau dessous dex_isur|x-x_i|=x-x_ialorsxPlus quex_iCe sera. Donc,Devenez le plus petitxau dessous de要素を保存する配列A_1とDevenez le plus petitxUn tableau qui stocke des éléments plus grandsA_2Préparez-en deuxest nécessaire(Si vous n'en préparez pas deux, la mise en œuvre sera assez compliquéealorsす。実装も工夫！).. Aussi, par celaO(1)alorsf(x)は計算alorsきますが、この計算sur解説を省略するのalors自分alors確認してみてください。

Ici aussi, il est nécessaire d'insérer $ O (\ log {n}) $ ou $ O (1) $ dans le tableau trié, mais dans le cas d'un tableau normal, cela coûte $ O (n) $. Je vais. Multiset peut être utilisé ici. ** multiset peut ajouter, supprimer et rechercher des données pour $ O (\ log {n}) $ respectivement ** (La structure interne est un arbre rouge et noir, je l'ai utilisé pour la première fois cette fois).

De plus, l'élément de $ A_1 $ doit toujours être inférieur ou égal à l'élément de $ A_2 $, et soit $ len (A_1) = len (A_2) $ soit $ len (A_1) = len (A_2) + 1 $ tient. , Le dernier élément de $ A_1 $ est minimisé par $ x $ ce qui minimise $ f (x) $, $ len (A_1) pour calculer $ f (x) $ par $ O (1) $ ), Len (A_2), sum (A_1), sum (A_2) $ doivent être préparés et ces variables doivent être mises à jour par la requête de mise à jour. il y a. La méthode de mise en œuvre est décrite dans le commentaire du code ci-dessous, donc si vous ne comprenez pas, veuillez vous y référer.

De plus, dans le code ci-dessous, il y a un code pour supprimer le premier élément et le dernier élément du multiset, mais si vous spécifiez la valeur de l'élément à supprimer, les éléments avec la même valeur seront supprimés en même temps, donc ** Spécifiez la plage à supprimer besoin de le faire **.

F.cc

//Comprendre(Ordre alphabétique)
#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<iterator>//Régler l'opération(Ensemble de produits,Ensemble de somme,Ensemble de différences, etc.)
#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
//pour la relation de 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.
#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--)
//x est un conteneur tel que vector
#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 MAX(x) *max_element(ALL(x)) //Trouvez la valeur maximale
#define MIN(x) *min_element(ALL(x)) //Trouvez la valeur minimale
//constant
#define INF 1000000000000 //10^12:Valeur extrêmement élevée,∞
#define MOD 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //10^5:Portée maximale de la baie(Utilisé pour l'énumération des nombres premiers, etc.)
//Abréviation
#define PB push_back //Insérer dans le vecteur
#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

//multiset Même type supprimé(Si c'est un effacement normal)
//Tout ce que vous avez à faire est de spécifier la plage avec l'itérateur
signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll q;cin >> q;
    multiset<ll> A1,A2;
    ll B=0;
    ll s1,s2;s1=0;s2=0;
    ll l1,l2;l1=0;l2=0;
    REP(i,q){
        ll x,a,b;cin >> x;
        if(x==1){
            cin >> a >> b;
            B+=b;
            if(i==0){
                A1.insert(a);
                l1+=1;
                s1+=a;
            //l1=Au moment de l2
            //Vérifiez avec l2 et mettez en l1 si c'est l'avant
            //Sinon, mettez le minimum de l2 dans l1
            //Mettez d'abord A2 et mettez le minimum en A1
            }else if((l1+l2)%2==0){
                s2+=a;
                A2.insert(a);
                ll j=*A2.begin();
                s1+=j;
                s2-=j;
                A1.insert(j);
                //A2.erase(j);
                A2.erase(A2.begin(),++A2.begin());
                l1+=1;
            //l1+1=Au moment de l2
            //Vérifier avec l1 et mettre en l2 à la fin
            //Sinon, mettez le maximum de l1 dans l2
            //Mettez d'abord A1 et mettez le maximum dans A2
            }else{
                s1+=a;
                A1.insert(a);
                ll j=*(--A1.end());
                s2+=j;
                s1-=j;
                A2.insert(j);
                A1.erase(--A1.end(),A1.end());
                l2+=1;
            }
        }else{
            ll j=*(--A1.end());
            cout << j << " " << -s1+s2+j*(l1-l2)+B << endl;
        }
    }
}