[PYTHON] AtCoder Débutant Contest 167 Évaluation
Les résultats de cette fois
✳︎ ac-predictor ne fonctionne pas et il n'y a pas de performance, mais c'était 1664.
Impressions de cette époque
Je pense que cela a fonctionné assez bien cette fois. C'était relativement facile à trouver car il y avait des questions similaires dans le passé en D et E. Cependant, il y avait des moments où l'implémentation était boguée, donc je veux éviter d'être impatient avec de tels bogues. De plus, j'ai bien considéré le problème F à la toute fin, je voudrais donc être prudent.
Problème A
Il vous suffit de juger si s est égal à la chaîne de caractères excluant la fin de t.
A.py
s=input()
t=input()
print("Yes" if s==t[:-1] else "No")
Problème B
Pensez à commencer par le plus grand nombre de cartes.
B.py
a,b,c,k=map(int,input().split())
if a>=k:
print(k)
elif a+b>=k:
print(a)
else:
print(a-(k-a-b))
Problème C
Il est temps d'effectuer une recherche complète en raison du problème C ... C'est difficile parce que le niveau des concurrents d'AtCoder monte et continue. Je ferai de mon mieux pour ne pas perdre.
Tout d'abord, envisagez une recherche complète (** Ne doutez pas du DP, d'abord une recherche complète **). Pour le moment, il vous suffit de penser au livre de référence à choisir et le montant du calcul à sélectionner est de $ O (n \ fois 2 ^ n) $. Le niveau de compréhension de chaque algorithme augmentera lors de la sélection d'un livre de référence ici est calculé par $ O (m) $, et après avoir décidé quel livre de référence sélectionner, si le niveau de compréhension de tous les algorithmes est X ou plus Puisque le jugement peut être fait avec $ O (m) $, il peut être calculé avec $ O (2 ^ n \ fois (n \ fois m + m)) = O (2 ^ n \ fois n \ fois m) $. Par conséquent, vous pouvez écrire un programme qui respecte la limite de temps. De plus, même si vous achetez tous les livres de référence, vous ne pourrez peut-être pas comprendre tous les algorithmes ci-dessus X, donc je l'ai initialisé avec inf (= 100000000000000000).
De plus, j'ai mis la ligne (✳︎) dans l'instruction for sur la ligne suivante pour la rendre boguée. C'est trop fou. Cependant, j'ai pu ** essayer la suppression des bogues avec un échantillon **, c'est donc un bon point.
C.py
n,m,x=map(int,input().split())
ca=[list(map(int,input().split())) for i in range(n)]
ans=100000000000000000
for i in range(2**n):
check=[0]*m
ans_=0
for j in range(n):
if ((i>>j)&1):
ans_+=ca[j][0]#(✳︎)
for k in range(m):
check[k]+=ca[j][k+1]
if all([l>=x for l in check]):
ans=min(ans,ans_)
if ans==100000000000000000:
print(-1)
else:
print(ans)
Problème D
Le moyen le plus simple est d'effectuer tous les k mouvements, mais cela n'est pas possible en raison de k contraintes. Ici, si vous déménagez n fois, ** il y a une ville i que vous visitez plus d'une fois ** (cette preuve est omise). De plus, comme les villes visitées plus d'une fois et visitées plus tard peuvent toujours être tracées à partir de la ville i, une boucle se forme dans les villes après la ville i jusqu'à la deuxième visite de la ville i ** (entrée). Dans l'exemple 1, une boucle de 1 → 3 → 4 est formée.) Par conséquent, pensez d'abord à découvrir une boucle, mais si vous enregistrez les villes que vous avez déjà visitées, vous pourrez découvrir la boucle lorsque vous visiterez une ville deux fois. De plus, je souhaite utiliser ** O (1) pour déterminer s'il y a une ville à visiter, je vais donc l'enregistrer en tant qu'ensemble **. En outre, ** enregistrez l'ordre de visite des villes **, donc enregistrez l'ordre de visite des villes dans un tableau. Si la boucle peut être déterminée par cela, le cas avant et après l'entrée dans la boucle et la partie de la boucle correspondant à K (mod) sont utilisés pour déterminer. Ce jugement, etc. n'est pas difficile (l'idée), donc je ne l'écrirai qu'en commentaire dans le code suivant.
answerD.py
#Enregistrer l'ordre de visite des villes dans un tableau
visited=[0]
#Enregistrez les villes que vous avez visitées en groupe
visited_set=set()
visited_set.add(0)
n,k=map(int,input().split())
a=list(map(int,input().split()))
#La ville où next1 visite maintenant, la ville où next2 se rend ensuite
#Quittez la boucle while si next2 est déjà visité
next1=0
next2=-1
while True:
#Vers la ville voisine
next2=a[next1]-1
#Faites-en la ville que vous visitez maintenant
next1=next2
if next2 in visited_set:
#Parce que c'est une ville que j'ai déjà visitée
break
else:
#Insérer dans le tableau dans l'ordre
visited.append(next2)
#Insérez dans un ensemble qui enregistre si vous avez visité
visited_set.add(next2)
#Si k est inférieur au nombre total de villes visitées, affichez la kème ville telle quelle
if k<len(visited):
print(visited[k]+1)
else:
#Trouvez la longueur de la boucle(J'ai tendance à faire une erreur ici, alors j'ai écrit un diagramme)
loop_len=(len(visited)-visited.index(next2))
#Jusqu'à ce que vous atteigniez la boucle
k-=(len(visited)-loop_len)
#Compte tenu du reste de la longueur de la boucle, il est facile de voir où vous en êtes dans la boucle.
print(visited[k%loop_len+visited.index(next2)]+1)
E problème
Personnellement, j'ai pensé que c'était plus facile que le problème D. Cependant, c'était un nouveau problème, donc je suis content de l'avoir trouvé pendant le concours (j'ai été surpris de le trouver).
Puisque n blocs sont alignés côte à côte et que la façon de peindre avec m couleur est susceptible d'être obtenue par O (1), j'ai supposé qu'il y avait $ l $ paires de blocs adjacents. Si vous décidez ici de la couleur des blocs du côté le plus à gauche, si les couleurs des blocs adjacents ne sont pas différentes, $ m \ times (m-1) \ times (m-1) \ times (m-1) \ times … Ce sera $. Par contre, si le deuxième bloc est le même, on peut voir que c'est $ m \ fois (m-1) \ fois 1 \ fois (m-1) \ fois… $. Par conséquent, j'ai pensé qu'il serait normal d'ignorer les parties de la même couleur dans ces blocs adjacents, j'ai donc décidé de ** connecter les blocs et de les considérer comme un seul bloc **. Par conséquent, s'il y a $ l $ paires de blocs adjacents, vous pouvez ** considérer une séquence de blocs de $ n-l $ de longueur qui ont tous des couleurs différentes **. De plus, il y a $ _ {n-1} C _ {l} $ selon le bloc qui a la même couleur, donc quand il y a $ l $ paires de blocs adjacents, la méthode de peinture de couleur est $ m . times (m-1) ^ {nl-1} \ times _ {n-1} C _ {l} $ Ce sera la même chose, et vous pouvez calculer cela avec $ l = 0 ~ k $. De plus, la réponse peut être très large, vous devez donc faire calcul de combinaison par inverse du mod (= 998244353). De plus, ici, si vous l'implémentez en faisant attention ** que le calcul de la puissance doit également être effectué sous mod (= 998244353) **, ce sera comme suit.
✳︎ Au fait, j'ai une bibliothèque de modint, donc je la posterai bientôt sous forme d'article.
answerE.cc
//Référence: http://ehafib.hatenablog.com/entry/2015/12/23/164517
//Comprendre(Ordre alphabétique,bits/stdc++.Une faction qui n'utilise pas h)
#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 998244353 //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
ll 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]*i%MOD;
inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
finv[i]=finv[i-1]*inv[i]%MOD;
}
}
//Calcul du coefficient binomial
ll 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]%MOD)%MOD;
}
ll modpow(ll a,ll n,ll mod){
ll res = 1;
while(n > 0){
if(n & 1) res = res * a % mod;
a = a * a % mod;
n >>= 1;
}
return res;
}
signed main(){
COMinit();
ll n,m,k;cin >> n >> m >> k;
ll ans=0;
REP(l,k+1){
ll ansx=1;
ansx*=COM(n-1,l);
ansx*=modpow(m-1,n-l-1,MOD);
ansx%=MOD;
ansx*=modpow(m,1,MOD);
ansx%=MOD;
ans+=ansx;
ans%=MOD;
}
cout << ans << endl;
}
F problème
C'est un problème de parenthèses qui apparaît souvent, mais je pense que c'était assez difficile. Cependant, je pense que je dois le résoudre même à première vue, donc je veux faire de mon mieux. Premièrement, lorsqu'il y a une chaîne de parenthèses, lorsque ** (vaut +1 et) est défini sur -1 et que la somme cumulée est considérée depuis le début, le total lorsque tous les éléments sont égaux à 0 ou plus et ajoutés à la fin est égal à 0. Tout ce dont tu as besoin c'est **. Ce problème est également difficile car cette condition doit être remplie dans la chaîne. Ici, pour le moment, j'ai pensé à concaténer dans l'ordre de celui avec la plus grande somme cumulée de chaque chaîne de caractères, mais tel quel, il est possible qu'il soit inférieur à 0 dans chaque chaîne de caractères, donc sous ceci Vous devez vous assurer que la somme cumulée dans cette chaîne est toujours positive. Par exemple, si la valeur minimale de la somme cumulée d'une certaine chaîne de caractères est égale ou supérieure à 0, la somme cumulée de tous les éléments sera toujours égale ou supérieure à 0 quel que soit l'ordre dans lequel ils sont connectés. Par conséquent, le problème est ** pour ceux dont la somme cumulée minimale des chaînes est inférieure à 0 **. Sur cette base, si vous faites attention au cas où la somme cumulative finale d'une certaine chaîne de caractères est égale ou supérieure à 0 **, si vous pouvez ajouter cette chaîne de caractères, la somme cumulée ne sera pas réduite et la valeur minimale à ce moment-là sera inférieure à 0. Plus la valeur est élevée, mieux c'est, il est donc préférable de concaténer avidement dans l'ordre décroissant de ** la somme cumulée minimale des chaînes de caractères **. En revanche, ** si la somme cumulée finale d'une chaîne est inférieure à 0 **, ** il n'est pas facile de décider avec gourmandise **. J'ai réfléchi à ce qui se passerait si je le faisais avec avidité, mais je peux le résoudre en regardant le blog de kmjp. Est fait. Inversez simplement la chaîne de caractères et pensez-y.
Je l'ai écrit jusqu'à présent, mais quand j'y repenserai plus tard, je ne le comprends pas tel quel, donc je donnerai presque la même explication ci-dessous en utilisant des ** diagrammes. Je suis désolé qu'il y ait de nombreuses parties qui se chevauchent. </ font>
Enfin, je voudrais résumer les points importants de ce numéro.
- Les parenthèses sont calculées en considérant (+1 et) comme -1.
- Le fait que la chaîne entre parenthèses soit valable et que la somme cumulée de tous les éléments soit égale ou supérieure à 0 et que la valeur finale soit 0 correspond à la même valeur.
- Les valeurs minimales et finales lorsque l'on considère la somme cumulée dans une chaîne de caractères contenant uniquement des parenthèses (y compris la chaîne de parenthèses) sont importantes.
- La valeur minimale de la somme cumulée étant égale ou supérieure à 0, pensez à ne pas tomber en dessous. Si vous souhaitez augmenter la somme cumulée, vous pouvez réfléchir avec gourmandise, mais si vous souhaitez diminuer la somme cumulée, vous devez penser à inverser la chaîne de caractères avec uniquement des parenthèses.
C'est difficile, mais je veux m'assurer que le prochain problème similaire trouvera une réponse correcte. Je pensais que c'était une bonne question qui méritait d'être examinée.
✳︎ Le deuxième code sera raccourci à la limite en utilisant les itertools que j'ai appris plus tôt. Veuillez vous référer à l'explication dans Cet article.
answerF.py
import sys
n=int(input())
s=[input() for i in range(n)]
t=[2*(i.count("("))-len(i) for i in s]
if sum(t)!=0:
print("No")
sys.exit()
st=[[t[i]] for i in range(n)]
for i in range(n):
now,mi=0,0
for j in s[i]:
if j=="(":
now+=1
else:
now-=1
mi=min(mi,now)
st[i].append(mi)
#st.sort(reverse=True,key=lambda z:z[1])
u,v,w=list(filter(lambda x:x[1]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]>=0,st)),list(filter(lambda x:x[1]<0 and x[0]<0,st))
v.sort(reverse=True)
v.sort(reverse=True,key=lambda z:z[1])
w.sort(key=lambda z:z[0]-z[1],reverse=True)
lu=len(u)
lv=len(v)
now2=0
for i in range(n):
if i<lu:
now2+=u[i][0]
elif i<lu+lv:
if now2+v[i-lu][1]<0:
print("No")
break
now2+=v[i-lu][0]
else:
#Non, ça ne va pas ici.
if now2+w[i-lu-lv][1]<0:
print("No")
break
now2+=w[i-lu-lv][0]
else:
print("Yes")
answerF_shorter_faster.py
from itertools import accumulate,chain
n,*s=open(0).read().split()
u=[[min(accumulate(chain([0],t),lambda a,b: a+(1 if b=="(" else -1))),2*t.count("(")-len(t)] for t in s]
m=0
for c,d in chain(sorted([x for x in u if x[1]>=0])[::-1],sorted([x for x in u if x[1]<0],key=lambda z:z[0]-z[1])):
if m+c<0:print("No");break
m+=d
else:print("No" if m else "Yes")
Recommended Posts