[PYTHON] Codeforces Round # 673 (Div.2) Examen Bacha (10/22)

Les résultats de cette fois

スクリーンショット 2020-10-22 18.05.52.png

Impressions de cette époque

J'écris un article sur la folie parce que je n'ai pas pu résoudre le problème D parce qu'il semblait résolu.

[Une addition] Si vous regardez de près, vous avez manqué les conditions évidentes. J'ai trop collé à la solution ... Ma tête est trop raide ...

Problème A

Sélectionnez $ i, j $ et ajoutez $ a \ _i $ à $ a \ _j $, de sorte que le nombre maximum d'opérations est de sélectionner le minimum $ a \ _i $ et d'effectuer l'opération **. Par conséquent, considérez le nombre maximum d'opérations lorsque vous opérez sur n'importe quel $ j $ sous $ i \ neq j $. Puisqu'il ne dépasse pas $ k $, $ [\ frac {k-a \ _ j} {a \ _ i}] $ est le nombre d'opérations en attente pour chaque $ j $.

A.py


for _ in range(int(input())):
    n,k=map(int,input().split())
    a=list(map(int,input().split()))
    m=min(a)
    l=a.index(m)
    ans=0
    for i in range(n):
        if i!=l:
            ans+=(k-a[i])//m
    print(ans)

Problème B

$ f (b) = (nombre total de paires de $ i \ <j $ tel que b \ _i + b \ _j $ = $ T $), et $ f ($ f de $ c, d $ divisé par $ a $) Envisagez de minimiser c) + f (d) $. À ce stade, je pensais que si vous mettez ** $ x $ dans un tableau différent de $ T-x $, ** les deux peuvent être mis à 0.

S'il s'agit de $ x \ neq Tx $, il tiendra toujours, mais s'il y a trois $ x $ ou plus tels que ** $ x = Tx \ leftrightarrow x = \ frac {T} {2} $ ** $ X = \ frac {T} {2} $ les éléments qui ne peuvent pas être mis à 0 sont $ k $, et $ c et d $ sont $ \ frac {k} {2}, k- \ frac, respectivement. $ f (c) + f (d) $ est le minimum lors du tri de {k} {2} $ pièces à la fois.

Par conséquent, les cas suivants sont classés.

(1) Quand $ T $ est impair Mettez les éléments sous $ [\ frac {T} {2}] $ dans $ c $ et les éléments plus grands que $ [\ frac {T} {2}] $ dans $ d $.

(2) Quand $ T $ est pair ** $ [] avec des éléments inférieurs à $ [\ frac {T} {2}] $ en $ c $ et des éléments supérieurs à $ [\ frac {T} {2}] $ en $ d $ indexez l'élément de frac {T} {2}] $ une fois dans $ cand $ **. Puisque la taille de $ cand $ est $ k $, nous allouerons respectivement $ \ frac {k} {2} et k- \ frac {k} {2} $ à $ c et d $.

B.py


for _ in range(int(input())):
    n,t=map(int,input().split())
    a=list(map(int,input().split()))
    ans=[-1]*n
    cand=[]
    for i in range(n):
        if t%2==0:
            if a[i]<t//2:
                ans[i]=0
            elif a[i]>t//2:
                ans[i]=1
            else:
                cand.append(i)
        else:
            if a[i]<=t//2:
                ans[i]=0
            else:
                ans[i]=1
    l=len(cand)
    for i in range(l):
        if i<l//2:
            ans[cand[i]]=0
        else:
            ans[cand[i]]=1
    print(" ".join(map(str,ans)))

Problème C

C'était un peu fastidieux à mettre en œuvre, mais c'est juste implémenté. Je pense que la politique est plus facile à établir que B.

Trouvez le plus petit élément de toute sous-colonne contiguë de $ k $ de longueur avec tout $ k $. Tout d'abord, il va de soi que ** $ k $ diminue de façon monotone au fur et à mesure de sa croissance. À ce stade, en faisant attention au moment où chaque valeur sort (** chute du client principal! **), ** la plus petite longueur de la sous-chaîne continue de la longueur $ k $ qui satisfait la condition d'une certaine valeur. J'ai pensé que je devrais demander $ k $ **.

Par conséquent, il existe un ensemble d'index $ x \ _1, x \ _1,…, x \ _l $ (indexés à 0 par ordre croissant) avec une certaine valeur de $ x $, puis $ x \ _ 0 = -1, x \ _ { Quand l + 1} = n $, $ x \ _ {i + 1} -x \ _i \ leqq mi $ devrait être valable pour tout $ 0 \ leqq i \ leqq \ {l} $. Par conséquent, $ mi = max (x \ _ {i + 1} -x \ _ i) $ est la solution. (Je pense qu'il est facile de voir les conditions pour établir ** dessiner un diagramme **.)

Par conséquent, puisque la longueur minimale du sujet peut être obtenue à partir de chaque valeur ($ O (n) $), nous envisagerons de trouver l'élément minimum qui sera la réponse. En d'autres termes, l'implémentation ressemble à ceci:

$ values $ = (un tableau de <valeurs, longueur minimale de sous-chaînes contiguës> paires stockées dans l'ordre croissant des valeurs) $ now $ = (longueur la plus longue sans élément minimum fixe) $ ans [i] $ = (le plus petit élément de toute sous-colonne contiguë de longueur $ i + 1 $)

** Vous pouvez décider dans l'ordre à partir du plus petit élément **, alors envisagez de regarder le $ i $ e élément de $ values $ dans l'ordre croissant de $ i $. À ce stade, lorsque $ values [i] .S $ est inférieur à $ now $, $ now $ à $ values [i] .S $ doit être $ values [i] .F $. Ensuite, $ now $ est mis à jour en $ values [i] .S-1 $. De plus, si $ values [i] .S $ est plus grand que $ now $, vous pouvez regarder l'élément suivant de $ values $ sans effectuer le processus de mise à jour. De plus, s'il existe une sous-colonne de longueur $ k $ pour laquelle le plus petit élément ne peut pas être déterminé, $ ans [k-1] $ doit être mis à -1, donc $ ans $ est initialement initialisé avec -1. Je vais le laisser.

C.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
//S'il n'y a pas de D, la variable de boucle est incrémentée de 1, et s'il y a un D, la variable de boucle est décrémentée 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

signed main(){
    //Spécification de sortie du nombre de chiffres fractionnaires
    //cout<<fixed<<setprecision(10);
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll t;cin>>t;
    REP(_,t){
        map<ll,vector<ll>> m;
        ll n;cin>>n;
        REP(i,n){
            ll a;cin>>a;
            m[a].PB(i);
        }
        vector<pair<ll,ll>> values;
        FORA(i,m){
            ll s=SIZE(i.S);
            ll mi=-1;
            REP(j,s){
                if(j==0){
                    mi=max(mi,i.S[j]+1);
                }
                if(j==s-1){
                    mi=max(mi,n-i.S[j]);
                }
                if(j!=s-1){
                    mi=max(mi,i.S[j+1]-i.S[j]);
                }
            }
            values.PB(MP(i.F,mi));
        }
        
        vector<ll> ans(n,-1);
        ll sv=SIZE(values);
        #if 0
        REP(i,sv){
            if(i==sv-1)cout<<values[i].F<<" "<<values[i].S<<"\n";
            else cout<<values[i].F<<" "<<values[i].S<<endl;
        }
        cout<<endl;
        #endif
        ll now=n;
        REP(i,sv){
            while(values[i].S<=now){
                ans[now-1]=values[i].F;
                now--;
            }
        }
        REP(i,n){
            if(i==n-1)cout<<ans[i]<<"\n";
            else cout<<ans[i]<<" ";
        }
    }
}

Problème D

Vous pouvez l'utiliser librement pour moins de 3n $ fois, alors considérez ** quand cela vous convient **. La première chose à noter est que vous pouvez ajuster la valeur en définissant ** $ i = 1 $ **. De plus, je pensais que cela ne pouvait pas être réalisé lorsque ** $ \ sum_ {i = 1} ^ {n} {a \ _i} $ était un multiple de $ n $ **, et cela pourrait être réalisé dans d'autres cas.

Ici, lorsque $ i = 1 $ est sélectionné, $ a \ _1 $ change dans le sens décroissant, donc je pense qu'il serait préférable de collecter autant d'éléments que possible dans ** $ i = 1 $ puis de les trier **. (Je n'ai pas pu terminer la discussion d'ici).

De plus, lors du déplacement d'un élément de $ a \ _i $ vers $ a \ _1 $, $ a \ _i $ sera laissé par $ a \ _i \ mod \ i $. Ici, ** Pour déplacer ce surplus vers $ a \ _1 $ ** Une fois que vous déplacez $ i-a \ _i \ mod \ i $ de $ a \ _1 $ à $ a \ _i $ Vous pouvez obtenir $ a \ _i = 0 $ en passant à nouveau de $ a \ _i $ à $ a \ _1 $. À ce stade, $ a \ _1 \ geqq i-1 \ geqq i-a \ _i \ mod \ i $ doit être satisfait, mais dans l'ordre croissant de ** $ i $, $ a \ _i $ à $ a \ _1 $ En supposant que l'élément est déplacé vers **, cette condition est satisfaite à partir de $ a \ 1 = \ sum {j = 1} ^ {i-1} a \ _i \ geqq i-1 $.

Par conséquent, ce qui précède est effectué dans l'ordre croissant de $ i $ pour faire $ a \ 1 = \ sum {i = 1} ^ {n} {a \ _i} $ (maximum $ 2 (n-1) $ fois) puis tout À propos de $ i $ Déplacer les éléments de $ a \ _1 $ vers $ a \ i $ de $ b (= \ frac {\ sum {i = 1} ^ {n} {a \ _ i}} {n}) $ En louant (jusqu'à $ n-1 $ fois), tous les éléments peuvent être égalisés à $ b $ jusqu'à 3 $ (n-1) $ fois au total.

D.py


for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    ans=[]
    if sum(a)%n!=0:
        print(-1)
        continue
    b=sum(a)//n
    for i in range(1,n):
        if a[i]%(i+1)==0:
            ans.append([i+1,1,a[i]//(i+1)])
            a[0]+=a[i]
            a[i]=0
        else:
            x=i+1-a[i]%(i+1)
            ans.append([1,i+1,x])
            a[0]-=x
            a[i]+=x
            ans.append([i+1,1,a[i]//(i+1)])
            a[0]+=a[i]
            a[i]=0
    for i in range(1,n):
        ans.append([1,i+1,b])
    l=len(ans)
    print(l)
    for i in range(l):
        print(" ".join(map(str,ans[i])))

Après le problème E

Je vais sauter cette fois.

Recommended Posts

Codeforces Round # 658 (Div.2) Examen Bacha (7/29)
Codeforces Round # 654 (Div.2) Critique Bacha (8/18)
Codeforces Round # 594 (Div.2) Examen Bacha (10/29)
Codeforces Round # 609 (Div.2) Critique Bacha (10/8)
Codeforces Round # 597 (Div.2) Examen Bacha (10/27)
Codeforces Round # 651 (Div.2) Critique Bacha (8/20)
Codeforces Round # 659 (Div.2) Critique Bacha (8/5)
Codeforces Round # 610 (Div.2) Critique Bacha (10/5)
Codeforces Round # 479 (Div.3) Examen Bacha (9/25)
Codeforces Round # 603 (Div.2) Examen Bacha (10/15)
Codeforces Round # 600 (Div.2) Examen Bacha (10/21)
Codeforces Round # 481 (Div.3) Examen Bacha (9/24)
Codeforces Round # 639 (Div.2) Examen Bacha (9/4)
Codeforces Round # 521 (Div.3) Examen Bacha (10/9)
Codeforces Round # 652 (Div.2) Examen Bacha (8/24)
Codeforces Round # 673 (Div.2) Examen Bacha (10/22)
Codeforces Round # 606 (Div.3) Examen Bacha (10/13)
Codeforces Round # 613 (Div.2) Examen Bacha (10/1)
Codeforces Round # 665 (Div.2) Examen Bacha (8/23)
Codeforces Round # 592 (Div.2) Examen Bacha (11/03)
Codeforces Round # 662 (Div.2) Critique Bacha (8/8)
Codeforces Round # 618 (Div.2) Examen Bacha (9/26)
Codeforces Round # 648 (Div.2) Critique Bacha (9/5)
Codeforces Round # 676 (Div.2) Examen Bacha (10/31)
Codeforces Round # 675 (Div.2) Examen Bacha (10/30)
Codeforces Round # 486 (Div.3) Examen Bacha (9/23)
Codeforces Round # 671 (Div.2) Examen Bacha (9/22)
Codeforces Round # 669 (Div.2) Examen Bacha (9/9)
Codeforces Round # 672 (Div.2) Examen Bacha (10/16)
Codeforces Round # 638 (Div.2) Examen Bacha (9/16)
Codeforces Round # 663 (Div.2) Examen Bacha (8/13)
Codeforces Round # 668 (Div.2) Examen Bacha (9/7)
Codeforces Round # 663 (Div.2) Examen Bacha (8/16)
Codeforces Round # 609 (Div.2) Examen Bacha (10/6)
Codeforces Round # 645 (Div.2) Critique Bacha (9/10)
Codeforces Round # 664 (Div.2) Examen Bacha (8/13)
Codeforces Round # 660 (Div.2) Critique Bacha (8/4)
Codeforces Round # 643 (Div.2) Révision
Codeforces Round # 679 (Div.2) Révision (10/25)
Codeforces Round # 657 (Div.2) Révision
Code de l'éducation forces Round 93 Bacha Review (8/17)
Code de l'éducation forces Round 94 Bacha Review (9/3)
Code de l'éducation forces Round 91 Bacha Review (7/28)
Code de l'éducation forces Round 88 Bacha Review (8/4)
Code de l'éducation forces Round 86 Bacha Review (9/17)
Code de l'éducation forces Round 89 Bacha Review (9/8)
Code de l'éducation forces Round 92 Bacha Review (7/30)
Code de l'éducation forces Round 90 Bacha Review (8/19)
Codeforces Round # 609 (Div.2) (jusqu'à B)
Code de l'Éducation Forces Round 87
Codeforces Beta Round # 13
Codeforces Beta Round # 1
Codeforces Beta Round # 2
DP100 Question Bacha Review 1 ~ 10 (8 / 26,27)
Codeforces Round # 626 B.Compte des sous-rectangles