[PYTHON] Codeforces Round # 481 (Div.3) Examen Bacha (9/24)

Les résultats de cette fois

Impressions de cette époque

Cette fois, j'ai pu le passer sans trop de bugs. C'est une bonne tendance, alors je vais continuer à faire de mon mieux.

Il y avait une partie qui est restée bloquée, mais j'aimerais faire de mon mieux pour pouvoir faire un mouvement stable comme celui-ci à chaque fois.

Problème A

Vu du côté droit de la séquence, ** assurez-vous que le même numéro n'apparaît pas deux fois **. Par conséquent, regardez les nombres du côté droit de la colonne des nombres et enregistrez le nombre qui apparaît dans $ s $ de l'ensemble. À ce stade, s'il n'est pas inclus dans $ s $, insérez-le dans la sortie du tableau ʻans` dans la réponse, et s'il est inclus, regardez le numéro suivant.

A.py

n=int(input())
a=list(map(int,input().split()))[::-1]
s={a[0]}
ans=[str(a[0])]
for i in range(1,n):
    if a[i] not in s:
        s.add(a[i])
        ans.append(str(a[i]))
print(len(ans))
print(" ".join(ans[::-1]))

Problème B

La chaîne de caractères peut être divisée en une partie continue et une partie non consécutive de $ x $ comme indiqué ci-dessous.

Si la longueur $ l $ de la partie continue de ce ** $ x $ peut être fixée à 2 ou moins **, le sujet est satisfait. De plus, comme le nombre minimum de suppressions requises pour cela est calculé par $ min (0, l-2) $, vérifiez combien de temps $ x $ est continu. Ici, vous pouvez facilement trouver la partie continue de ** $ x $ en utilisant la fonction groupby comme suit.

B.py

from itertools import groupby
n=int(input())
s=[]
for i in groupby(input(),lambda x:x=="x"):
    s.append(list(i[1]))
#s=list(groupby(input(),lambda x:x=="x"))
ans=0
for i in s:
    if i[0]=="x":
        ans+=max(0,len(i)-2)
print(ans)

Problème C

C'est un problème de ** restaurer chaque numéro de dortoir et numéro de chambre dans le dortoir à partir du numéro de chambre pour tous les dortoirs **. Pour le moment, j'ai noté les numéros de chambre de tous les dortoirs comme suit afin de comprendre quels sont les chiffres.

Faites également attention à la ** chambre avec le plus petit numéro de chambre ** dans chaque dortoir, $ 1 \ rightarrow 1 + a \ _1 \ rightarrow 1 + a \ _1 + a \ _2 \ rightarrow… \ rightarrow 1 + a \ _1 + Puisqu'il s'agit de la somme cumulée de a \ _2 +… + a \ _ {n-1} $, enregistrez-la sous le tableau $ s $. À ce stade, si le numéro de chambre donné est $ b \ _i $, le dortoir dans lequel vous vous trouvez correspondra à l'index du plus grand élément sous $ b \ _i $ dans le ** tableau $ s $ ** ( $ bissecter $ _ $ droit $). De plus, le numéro de chambre du dortoir ne doit être pris en compte qu'à partir de $ b \ _i $, qui est la différence par rapport au plus grand facteur obtenu précédemment.

Si vous faites ce qui précède pour n'importe quel $ i $, vous pouvez résoudre ce problème avec $ O (m \ log {n}) $.

C.py

n,m=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
from itertools import accumulate
s=list(accumulate([1]+a))[:-1]
from bisect import bisect_right
#print(s)
ans=[]
for i in range(m):
    c=bisect_right(s,b[i])-1
    #print(c)
    ans.append(str(c+1)+" "+str(b[i]-s[c]+1))
for i in range(m):
    print(ans[i])

Problème D

C'est un problème que j'ai pu voir, mais j'ai pu implémenter le code assez rapidement, donc j'ai ressenti un peu les récentes réalisations de Bacha.

Si vous pensez avidement, vous avez beaucoup de liberté, alors j'ai décidé de ** le réparer quelque part **. À ce moment, j'ai décidé de ** réparer les deux extrémités **. À ce stade, il y a un total de 9 cas où les deux extrémités de $ a [0] et a [n-1] $ ne sont pas modifiées par $ -1,0 ou + 1 $.

Par conséquent, nous allons envisager de définir une fonction $ check $ qui retourne le nombre d'opérations en fonction des changements aux deux extrémités. Tout d'abord, ** $ abs (a [n-1] -a [0]) $ pour créer une séquence d'égalité pour $ a [0], a [n-1] $ après le changement. Doit être un multiple de $ n-1 $ ** (renvoie $ inf $ s'il n'est pas un multiple de $ n-1 $). La ** tolérance à ce moment est $ \ frac {a [n-1] -a [0]} {n-1} $ **. Par conséquent, $ a [1] -a [0], a [2] -a [1],…, a [n-1] -a [n-2] $ sont tous $ \ frac {a [n-1] ] -a [0]} {n-1} $ Nous vérifierons avidement ** de face. A ce moment, si $ + 1 ou -1 $ est changé et qu'il devient $ \ frac {a [n-1] -a [0]} {n-1} $, le changement est effectué avec avidité. , Comptez les opérations à modifier. Aussi, s'il y a un élément dont la tolérance ne devient pas $ \ frac {a [n-1] -a [0]} {n-1} $ pour tout changement de $ + 1,0, -1 $, cette fois Renvoie $ inf $. Si tous les jugements ci-dessus sont effacés, le nombre d'opérations comptées est renvoyé.

À partir de ce qui précède, le nombre d'opérations dans chacune des 9 manières peut être calculé et la valeur minimale est sortie. De plus, si ** la valeur minimale est $ inf $ **, la condition n'est pas remplie, donc -1 est affiché.

Sachez également que si vous l'implémentez vous-même, vous pouvez faire une erreur ** sans compter le nombre d'opérations aux deux extrémités **. De plus, je pensais qu'il serait difficile de classer les cas, donc dans le cas de ** $ n = 1,2 $, je produis 0 en premier **. De plus, j'avais l'impression que j'allais faire une erreur si la tolérance était négative, alors dans ce cas, je l'ai retournée pour rendre la tolérance non négative.

D.py

n=int(input())
b=list(map(int,input().split()))
if n==1 or n==2:
    print(0)
    exit()
inf=10**12
#x,y est le montant du changement(0,-1,+1),9 façons
def check(x,y):
    global b,n
    ret=0
    if x!=0:
        ret+=1
    if y!=0:
        ret+=1 
    a=[i for i in b]
    a[0]+=x
    a[n-1]+=y
    #Dans l'ordre croissant
    if a[n-1]<a[0]:
        a=a[::-1]
    if (a[n-1]-a[0])%(n-1)!=0:
        return inf
    d=(a[n-1]-a[0])//(n-1)
    for i in range(n-1):
        if a[i+1]-a[i]==d:
            pass
        elif a[i+1]-a[i]==d+1:
            a[i+1]-=1
            ret+=1
        elif a[i+1]-a[i]==d-1:
            a[i+1]+=1
            ret+=1
        else:
            return inf
    return ret

ans=inf
for i in range(-1,2):
    for j in range(-1,2):
        ans=min(ans,check(i,j))
        #print(i,j,check(i,j))
if ans==inf:
    print(-1)
else:
    print(ans)

E problème

Il y a eu un cas auquel j'ai oublié de penser, et j'ai émis 2WA, donc je le regrette. Si vous pensez calmement, cela aurait dû être supprimé à au moins 1WA.

Tout d'abord, pour réfléchir au type de valeur valide, considérez d'abord la condition comme ** avec seulement ** $ x $ personnes. À ce moment, le changement du nombre de personnes à l'arrêt de bus $ i $ ème est $ a \ _i $, donc après avoir passé chaque arrêt de bus, $ x + a \ _0, x + a \ _0 + a \ _1,…, x + a Seul \ _0 + a \ _1 +… + a \ _ {n-1} $ est à bord. Par conséquent, vous pouvez voir que ** tous ces éléments doivent être 0 ou plus et $ w $ ou moins ** (✳︎). Par conséquent, $ a \ _0, a \ _0 + a \ _1,…, a \ _0 + a \ _1 +… + a \ _ {n-1} $ est calculé par la somme cumulée, et les valeurs maximale et minimale de celle-ci sont calculées. Disons respectivement $ u et d $. Ici, si $ x + u \ leqq w $ et $ x + d \ geqq 0 $ sont satisfaits, (✳︎) sera satisfait lors du passage d'un arrêt de bus (** Attention uniquement aux valeurs maximum et minimum! **). Vous devez également rencontrer ** $ 0 \ leqq x \ leqq w $ ** (c'était 2WA parce que j'ai oublié cela, désolé). Par conséquent, $ x + u \ leqq w $ et $ x + d \ geqq 0 $ et $ 0 \ leqq x \ leqq w $ sont satisfaits. Vous pouvez trouver le nombre d'entiers $ x $ qui satisfont \ leqq x \ leqq min (w, wu) $, et ** considérer le cas où il n'y a pas de partie commune **, puis $ min (0, min (w, wu) ) -Max (0, -d) + 1) $.

(Ce qui précède est une considération cohérente et la mise en œuvre est simple, mais pendant le concours, elle est devenue ** implémentation et considération sales **. Je le regrette.)

E.py

n,w=map(int,input().split())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
u,d=max(b),min(b)
print(max(0,min(w,w-u)-max(0,-d)+1))

E2.py

#Mise en œuvre pendant le concours
n,w=map(int,input().split())
a=list(map(int,input().split()))
from itertools import accumulate
b=list(accumulate(a))
u,d=max(b),min(b)
if u-d>w:
    print(0)
    exit()
if u>w:
    print(0)
    exit()
ran=[max(0,-d),min(w,w-u)]
if ran[1]<ran[0]:
    print(0)
    exit()
print(ran[1]-ran[0]+1)

Problème F

C'était dangereux parce que je l'ai mal lu au début. Premièrement, comme paramètre de problème, s'il y a deux personnes, $ a, b $, $ r \ _a > r \ _b $ et $ a, b $ ne se disputent pas, $ a $ sera le mentor de $ b $. pouvez.

Ici, si seule la première condition est utilisée, elle peut être facilement obtenue en récupérant l'index avec $ bisect $ _ $ left $ en ayant ** $ r $ valeurs dans l'ordre croissant ** (** Grand et petit). Sont comptés par ordre croissant! **). De plus, si vous ajoutez la deuxième condition après avoir considéré la première condition, vous pouvez voir que ** excluant ceux qui se disputent tout en satisfaisant une condition **.

Par conséquent, le nombre de personnes que la $ i $ ème personne ($ r \ _i $) peut encadrer est ** (le nombre de personnes ayant des compétences inférieures à ① $ r \ _i $) - (② $ r \ _i $ Le nombre de personnes peu qualifiées mais qui se disputent) **. De plus, $ check [i]: = $ (le nombre de personnes dont les compétences sont inférieures à $ r \ _i $ dans la $ i $ ème personne qui se dispute), $ p: = $ (les compétences de chaque personne) $ Check $ sera compté lorsque vous recevrez une paire de querelles, et $ p $ triera simplement l'entrée. Par conséquent, ① correspond à l'index (indexé à 0) lorsque $ bisect $ _ $ left (p, r \ _ i) $ est appliqué, et ② correspond à $ check [i] $.

À partir de ce qui précède, déplacez $ i $ dans l'ordre, stockez la réponse dans le tableau $ ans $, puis affichez-la comme réponse. De plus, le montant du calcul est de $ O (k + n \ log {n}) $.

F.py

n,k=map(int,input().split())
r=list(map(int,input().split()))
check=[0]*n
for i in range(k):
    x,y=map(int,input().split())
    x-=1
    y-=1
    if r[x]>r[y]:
        check[x]+=1
    if r[y]>r[x]:
        check[y]+=1
from bisect import bisect_left
ans=[0]*n
p=sorted(r)
for i in range(n):
    b=bisect_left(p,r[i])
    ans[i]=str(b-check[i])
print(" ".join(ans))

Problème G

Je me suis demandé s'il y avait trop de place pour le calcul et si l'énoncé du problème était long, mais j'ai raté le rythme rien qu'en l'implémentant. De plus, même si je ne l'ai implémenté que, il a fallu environ 30 minutes pour le résoudre, alors j'aimerais faire un effort pour le faire passer dans environ la moitié du temps.

Premièrement, les deux points suivants sont souvent négligés dans l'énoncé du problème.

・ Vous ne pouvez pas passer plusieurs examens en une journée, mais il n'y a pas de telle entrée en raison de la limitation du problème. ・ La préparation ne doit pas être continue

A ce moment, j'ai pensé que je pourrais utiliser la méthode gourmande ** qui se prépare à partir de l'examen le plus proche de la date de l'examen. Cette méthode gourmande est correcte car il n'y a aucun avantage à préparer d'abord des dates d'examens éloignées. Cela peut également être démontré par le fait que même si une date de test éloignée est préparée en premier, elle sera remplacée par une préparation pour une date de test plus proche **. Par conséquent, nous allons implémenter cette méthode gourmande ci-dessous.

Commencez par préparer les quatre structures de données suivantes. Les raisons pour lesquelles chacune est nécessaire seront décrites plus loin. De plus, vous devez initialiser ① et ②, mais je n'expliquerai pas cela car il peut être facilement traité après réception de l'entrée.

① Séquence $ examens [i]: = $ (Une séquence contenant le test (date du test, nombre requis de jours de préparation) pour laquelle la préparation peut commencer le jour $ i $) ② Arrangement $ ind [i]: = $ ($ i $ day est l'ordre de réception du test à la date du test, mais -1 s'il n'y a pas de date de test) ③ Array $ ans [i]: = $ (réponse à afficher le jour $ i $) ④ Set $ cand: = $ (Arrangement tenant (date du test, nombre requis de jours de préparation) du test prêt)

Tout d'abord, préparez ④ ** à tenir dans l'ordre croissant de la date du test afin de vous préparer au test qui est proche de la date du test. Cela vous permet de préparer à partir du plus petit élément de $ cand $ chaque jour. De plus, d'autres examens seront disponibles le ** $ i $ jour **. Tout ce que vous avez à faire est d'insérer ① dans $ cand $ et d'insérer tout le contenu de $ examens [i] $. Ensuite, ** si ce jour est le jour du test ** n'est pas prêt, considérez donc le jour suivant avec $ ans [i] $ comme $ m + 1 $. Ceci peut être déterminé par si $ ind [i] $ est -1 si ② est préparé, et si $ ind [i] $ n'est pas -1, considérez l'opération suivante.

Nous envisagerons de ** préparer ** sur la base du jugement ci-dessus, mais $ cand $ peut être vide. Dans ce cas, nous ne sommes pas prêts, alors considérez le jour suivant avec $ ans [i] = 0 $. Alors préparez-vous. Lors de la préparation, il vous suffit de regarder l'examen minimum $ cand $ ** (le montant de la mise en œuvre a légèrement augmenté car vous ne l'avez pas remarqué pendant le concours). De plus, si ** la date du test du test est déjà passée **, la préparation n'est pas à temps, donc -1 est sorti et le programme est terminé. Dans d'autres cas, vous pouvez prendre des mesures pour le test et substituer $ ind $ à l'ordre de réception de l'entrée de test dans $ ans [i] $. De plus, si vous devez encore vous préparer après la préparation du test, supprimez-le de ** $ cand $, décrémentez le nombre requis de jours de préparation de -1 et insérez-le à nouveau **.

Après avoir fait ce qui précède tous les jours, vous pouvez générer $ ans $, mais vous devez considérer la possibilité qu'il y ait encore des éléments dans ** $ cand $ **. Dans ce cas, ** est synonyme de certains tests qui ne sont pas prêts à temps **, donc -1 est affiché. Dans tous les autres cas, $ ans $ est affiché car la préparation du test est à temps pour tous les tests.

(Le code ci-dessous est implémenté pour ne pas être un gaspillage, et la considération ci-dessus n'est pas non plus gaspillée, mais pendant le concours, c'était un code qui pouvait faire beaucoup d'erreurs telles que ** branchement conditionnel **. Cela fonctionne avec des réflexes C'est aussi bien, mais il peut être préférable de le mettre en œuvre après avoir approfondi un peu plus la considération.)

G.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

signed main(){
    //Code pour accélérer la saisie
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m;cin>>n>>m;
    vector<vector<ll>> exams(n);
    //Pour le jour où c'est prêt
    vector<vector<pair<ll,ll>>> preparation(n);
    //Ind pour la date du test
    vector<ll> ind(n,-1);
    REP(i,m){
        ll s,d,c;cin>>s>>d>>c;
        exams[i]={s-1,d-1,c};
        ind[d-1]=i;
        preparation[s-1].PB(MP(d-1,c));
    }
    vector<ll> ans(n,-1);
    set<pair<ll,ll>> cand;
    REP(i,n){
        REP(j,SIZE(preparation[i])){
            cand.insert(preparation[i][j]);
        }
        if(ind[i]!=-1){
            ans[i]=m+1;
            continue;
        }
        if(SIZE(cand)==0){
            ans[i]=0;
            continue;
        }
        auto j=cand.begin();
        while(j!=cand.end()){
            if(j->S==0){
                j=cand.erase(j);
            }else{
                if(j->F<i){
                    cout<<-1<<endl;
                    return 0;
                }
                ans[i]=ind[j->F]+1;
                pair<ll,ll> p=*j;p.S-=1;
                cand.erase(j);
                if(p.S!=0){
                    cand.insert(p);
                }
                break;
            }
        }
        if(ans[i]==-1)ans[i]=0;
    }
    if(SIZE(cand)==0){
        REP(i,n){
            if(i==n-1)cout<<ans[i]<<endl;
            else cout<<ans[i]<<" ";
        }
    }else{
        auto j=cand.begin();
        while(j!=cand.end()){
            if(j->S!=0){
                cout<<-1<<endl;
                return 0;
            }
        }
        REP(i,n){
            if(i==n-1)cout<<ans[i]<<endl;
            else cout<<ans[i]<<" ";
        }
    }

}