[PYTHON] Codeforces Round # 521 (Div.3) Examen Bacha (10/9)
Les résultats de cette fois
Impressions de cette époque
C'était un problème qui devait être résolu jusqu'en F1, mais cela rendait DP buggy. J'avais une politique de base, mais je me demandais s'il fallait corriger la destination de la transition ou la source de la transition **, ou j'ai fait une erreur dans l'index **, donc je le regrette.
Problème A
C'était un problème que je pouvais voir dans le problème C d'ABC. Si vous regardez une opération qui avance avec $ a $ et retourne avec $ b $, cette opération est effectuée $ [\ frac {k} {2}] $ fois. De plus, dans le cas de $ k $, il avance de $ a $ une fois de plus à la fin, vous pouvez donc trouver le total ci-dessus.
A.py
for _ in range(int(input())):
a,b,k=map(int,input().split())
ans=(a-b)*(k//2)
if k%2==0:
print(ans)
else:
print(ans+a)
Problème B
Empêche la chaîne $ 101 $ d'apparaître. Pour de tels problèmes, considérez d'abord la ** méthode de l'avidité **.
Par exemple, regardons les caractères qui peuvent être de 101 $ à partir de la gauche. Autrement dit, $ i $ = 1 ~ $ n-2 $ donne $ a [i-1: i + 2] = "101" $. À ce stade, il est nécessaire de changer 1 de chaque côté de 0 en 0, mais comme il n'y a rien sur le côté gauche qui vaut déjà 101 $, il est préférable de changer 1 sur le côté droit en 0 ** Répétez ceci et comptez le nombre de fois que vous l'avez changé à 0.
B.py
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(1,n-1):
if a[i-1]==1 and a[i]==0 and a[i+1]==1:
a[i+1]=0
ans+=1
print(ans)
Problème C
La politique a été immédiate, mais j'ai intégré un bug dans le mystère.
Tout d'abord, supposons que vous excluez ** $ a [j] $ ** (supposons que la colonne numérique restante soit $ b $). A ce moment, $ sum (a) -a [j] = 2 \ times b \ _ {max} $ devrait tenir. Vous pouvez également sélectionner $ b_ {max} $ autre que $ a [j] $. Ici, $ sum (a) $ est calculé à l'avance et $ a [j] $ est donné, donc quand ** $ a [j] $ est donné, $ b \ _ {max} $ est accéléré. Pensez à ce que vous attendez de **. Premièrement, quand il y a deux éléments ou plus qui deviennent $ a \ _ {max} $, ** toujours $ b \ _ {max} = a \ _ {max} $ **, donc pour tout $ j $, respectivement. Il peut être jugé par $ O (1) $. Ensuite, s'il n'y a qu'un seul élément qui devient $ a \ _ {max} $, ** enregistrez le deuxième plus grand élément **, et $ a [j] = a \ _ {max} $ Seulement lorsque $ a [j] $ est exclu, $ b \ _ {max} = $ (le deuxième élément le plus grand) doit être défini. À ce moment également, le jugement peut être rendu avec $ O (1) $.
J'ai pu porter un jugement, mais parce que j'ai trié en trouvant le plus grand élément et le deuxième élément, ** l'index que je cherchais était différent du sujet **. Par conséquent, j'ai essayé de stocker la valeur qui satisfait le sujet dans le jugement précédent dans $ set $ pour le moment, et enfin de trouver l'index de l'élément inclus dans $ set $.
C.py
n=int(input())
b=list(map(int,input().split()))
a=sorted(b)
s=sum(a)
ans=set()
if a[-2]==a[-1]:
ma=a[-1]
for i in range(n):
if s-a[i]==2*ma:
ans.add(a[i])
else:
ma1,ma2=a[-1],a[-2]
for i in range(n):
if i==n-1 and s-a[i]==2*ma2:
ans.add(a[i])
if i!=n-1 and s-a[i]==2*ma1:
ans.add(a[i])
realans=[]
for i in range(n):
if b[i] in ans:
realans.append(str(i+1))
print(len(realans))
print(" ".join(realans))
Problème D
J'ai fait une erreur dans la mise en œuvre et j'étais impatient.
Je vais le couper, mais je ne considère pas l'ordre, donc je vais gérer combien de chaque nombre sort dans le dictionnaire $ c $. À ce stade, si vous ne savez pas combien de fois couper, vous ne saurez pas comment inclure l'élément dans $ t $. Par conséquent, supposons que nous ne coupions que ** $ x $ fois ** et poursuivons la discussion. Ici, si le nombre $ i $ dans $ c $ n'est inclus que dans $ c [i] $, alors $ t $ contient $ i $ dans seulement $ \ frac {c [i]} {x} $. Peut être inclus. Par conséquent, si vous vérifiez ceci pour tout $ i $ géré dans le dictionnaire, vous pouvez trouver le $ t $ ** le plus long en coupant ** $ x $ fois. Ici, si la plus longue longueur de ** $ t $ est supérieure ou égale à $ k $, alors ** le sujet $ t $ peut être construit. De plus, en augmentant le nombre de coupes , la longueur de $ t $ diminue de façon monotone ** de sorte qu'elle devient (la plus longue longueur de $ t $ en coupant $ x $ fois) $ \ geqq k $. Je veux trouver le plus gros $ x $, donc je le trouverai par dichotomie (✳︎). De plus, vous pouvez afficher $ t [: k] $ lorsque les éléments $ x $ ( obtenus doivent être affichés uniquement $ k $ **, notez qu'ici 1WA ).
(✳︎)… La dichotomie est créée en se référant à cet article. Notez que les rôles de ** $ l, r $ sont inversés ** car nous voulons trouver la valeur initiale de ** $ l, r $ ** et la valeur maximale cette fois.
D.py
n,k=map(int,input().split())
s=list(map(int,input().split()))
from collections import Counter
c=Counter(s)
z=dict()
def f(x):
global n,k,c,z
if x>n:return False
if x==0:return True
ret=0
z=dict()
for i in c:
ret+=c[i]//x
z[i]=c[i]//x
#print(x,ret)
return ret>=k
#l:True,r:False
l,r=0,10**6
while l+1<r:
y=l+(r-l)//2
if f(y):
l=y
else:
r=y
f(l)
#print(z)
ans=[]
for i in z:
for j in range(z[i]):
ans.append(str(i))
print(" ".join(ans[:k]))
E problème
Cela a pris beaucoup de temps en raison d'une erreur de mise en œuvre dans tous les C, D et E. Je vais me consacrer. De plus, TL semblait être dur sur ce problème et je l'ai publié en C ++, mais c'était un bon choix.
Au début, j'ai mal lu le problème ** et remarqué en regardant l'exemple. Depuis $ pairwise \ distinct $, chaque concours ne peut traiter que des problèmes sur le même sujet, et les problèmes sur un sujet ne peuvent être inclus que dans un seul concours.
Par conséquent, comptez le nombre de problèmes dans chaque sujet et enregistrez-les une fois sur la carte. De plus, puisque les ** numéros de sujets ne sont pas nécessaires **, seul le nombre de problèmes est stocké dans le tableau $ a $ ($ a $ est trié, la raison sera expliquée plus tard).
** Si le premier nombre n'est pas décidé, le nombre qui suit ne sera pas décidé **, alors laissez le premier nombre être $ x $. De plus, $ x $ est supérieur à 1 et inférieur à 2 $ \ fois 10 ^ 5 $. Pour le moment, le nombre de questions de $ x, 2x, 4x… $ est requis pour ouvrir chaque concours. De plus, comme le nombre maximum de questions pour chaque sujet est de 10 $ ^ 5 $, le nombre maximum de jours pour le concours est d'environ 20 $ jours ** ($ \ parce que \ 10 ^ 5 \ <2 ^ {20} $). J'ai remarqué qu'il y en avait. De plus, lors de l'ouverture d'un concours avec des questions $ y $, il va de soi que vous pouvez ouvrir autant de concours que possible ** après cela en choisissant le sujet ** avec le plus petit nombre de questions ci-dessus ** $ y $ **. .. Par conséquent, si vous triez $ a $ plus tôt, utilisez $ lower $ \ _ $ bound $ in $ a $ pour compter dans l'ordre s'il y a des sujets avec le nombre de problèmes $ x → 2x → 4x →… $. Je peux y aller. De plus, si la valeur de retour de $ lower $ \ _ $ bound $ est $ end $, les concours suivants ne peuvent pas être ouverts, le comptage s'arrêtera. De plus, ** vous ne pouvez pas sélectionner de questions pour les concours que vous avez déjà sélectionnés **, stockez donc les sujets que vous avez sélectionnés dans une variable appelée $ nxt $.
Selon la politique ci-dessus, le nombre de jours pendant lesquels le concours peut être organisé pour chaque $ x $ et le nombre de questions incluses peuvent être calculés par $ O ((\ log {n}) ^ 2) $, de sorte que le montant total du calcul est de O $ ( Il devient n (\ log {n}) ^ 2) $. Dans le cas de PyPy, même $ O (n \ log {n}) $ est inquiétant, donc je l'ai écrit en C ++ depuis le début.
E.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;cin>>n;
map<ll,ll> b;
REP(i,n){
ll z;cin>>z;
b[z-1]++;
}
vector<ll> a;
FORA(i,b){
if(i.S!=0)a.PB(i.S);
}
sort(ALL(a));
//REP(i,SIZE(a))cout<<a[i]<<endl;
ll ans=0;
FOR(x,1,200000LL){
//Rechercher à partir de nxt ou version ultérieure
ll ans_sub=0;
ll y=x;
auto nxt=a.begin();
while(true){
if(nxt==a.end())break;
nxt=lower_bound(nxt,a.end(),y);
if(nxt==a.end())break;
nxt++;
ans_sub++;
y*=2;
}
ans=max(ans,x*(1LL<<ans_sub)-x);
}
cout<<ans<<endl;
}
Problème F1
(L'énoncé du problème était difficile à lire.)
Au moment où vous le voyez, vous pouvez voir à quoi il ressemble DP. À ce stade, au moins un élément à republier dans une ligne de $ k $ ($ \ leftrightarrow $ **) est inférieur à $ k $ et la distance à l'élément le plus proche à droite (idem pour la gauche) est inférieure à $ k $. , La distance au bord est de $ k-1 $ ou moins **), donc ** des informations sur le dernier élément republié ** sont requises, et le nombre d'éléments finalement republiés est $ x $. À partir de là, j'ai réalisé que j'avais également besoin d'informations sur le nombre d'éléments qui étaient ** $ repost $ **. Par conséquent, le DP suivant est défini.
$ dp [i] [j] [l]: = $ (lorsque le nombre d'éléments republiés jusqu'au $ i $ ème élément est $ j $ et le dernier élément sélectionné est le $ l $ ème élément Total maximum d'éléments republiés)
Ensuite, considérez la transition. La valeur de $ dp $ est initialisée avec -1 (correspondant à -INF), et seul $ dp [0] [1] [0] $ est rendu $ a [0] $.
** Considérez la transition avec ou sans sélection de cet élément **. Considérez la destination de la transition en fonction de la sélection ou non de l'élément $ i + 1 $ ème en fonction de la source de transition de $ dp [i] [j] [l] $. De plus, les opérations suivantes sont effectuées lorsque $ dp [i] [j] [l]! = -1 $.
① Lors du choix de cet élément
Lorsque $ i = $ 0 ~ $ k-2 $, vous pouvez le sélectionner quelle que soit la valeur de ** $ l $ **, vous pouvez donc le sélectionner si $ j! = X $. Quand $ i = k-1 $ ~ $ n-2 $, il faut être $ (i + 1) -l \ leqq k $ en plus de $ j! = X $.
De plus, lorsque $ i = $ 0 ~ $ k-2 $, ** est requis lors de la sélection de l'élément $ i + 1 $ e pour la première fois **
Doit être fait en premier.
② Lorsque vous ne choisissez pas cet élément
S'il n'est pas sélectionné, il n'y a pas de condition, seul $ i $ est incrémenté de +1.
Faire ce qui précède termine dp. Aussi, lorsque je cherche une réponse, je voudrais trouver le maximum $ dp [n-1] [x] [l] $ avec n'importe quel $ l $, mais ** $ n-1-l \ leqq k \ leftrightarrow l Notez qu'il doit être \ geqq n-1-k $ **.
F1.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,k,x;cin>>n>>k>>x;
vector<ll> a(n);REP(i,n)cin>>a[i];
if(k==1){
if(x!=n){
cout<<-1<<endl;
}else{
cout<<accumulate(ALL(a),0LL)<<endl;
}
return 0;
}
//Initialisation pour une raison quelconque
//Si non-1
vector<vector<vector<ll>>> dp(n,vector<vector<ll>>(x+1,vector<ll>(n,-1)));
//Initialisation(Choisissez-vous je)
dp[0][1][0]=a[0];
REP(i,k-1){
//Lors du choix pour la première fois
dp[i+1][1][i+1]=a[i+1];
REP(j,x+1){
REP(l,n){
if(true){
if(dp[i][j][l]!=-1){
//Lors du choix
if(j!=x){
dp[i+1][j+1][i+1]=max(dp[i+1][j+1][i+1],dp[i][j][l]+a[i+1]);
}
//Si tu ne choisis pas
dp[i+1][j][l]=max(dp[i+1][j][l],dp[i][j][l]);
}
}
}
}
}
//transition
FOR(i,k-1,n-2){
REP(j,x+1){
REP(l,n){
if(true){
if(dp[i][j][l]!=-1){
//Lors du choix
if(j!=x and (i+1)-l<=k){
dp[i+1][j+1][i+1]=max(dp[i+1][j+1][i+1],dp[i][j][l]+a[i+1]);
}
//Si tu ne choisis pas
dp[i+1][j][l]=max(dp[i+1][j][l],dp[i][j][l]);
}
}
}
}
}
//Gamme ici
ll ans=-1;
FOR(l,n-1-(k-1),n-1){
ans=max(ans,dp[n-1][x][l]);
}
cout<<ans<<endl;
}
Problème F2
Je vais sauter cette fois.
Recommended Posts