[PYTHON] concours yukicoder 261 avis
résultat
Impressions
J'ai continué à bugger le problème C que je pensais facile, c'est douloureux ... Bien que je sois mort dans une grosse explosion, j'ai pu résoudre le problème C à la dernière minute, et quand j'étais calme, j'ai pu résoudre quatre questions, donc je continuerai mes efforts tels quels.
Problème A
Ce ne sera pas si grand, vous pouvez donc le faire 100 fois.
A.py
def calc(n):
ret=0
while n!=0:
ret+=(n%10)
n//=10
return ret
N=int(input())
for i in range(100):
N=calc(N)
print(N)
Problème B
Je pensais que ce serait difficile si $ N $ était pair, et quand j'ai regardé en arrière après le concours, $ N $ était seulement impair. C'est très décevant de connaître le motif étrange en environ 5 minutes ...
Dans le cas d'une telle construction, il est difficile de se prononcer sur les nuages sombres, alors ** je pense que je décide des règles moi-même en premier **. Cette fois, ** décidez que les nombres sont continus sur chaque ligne. De plus, lorsque $ N = 5 $, j'ai considéré les deux modèles suivants, mais dans le premier modèle, les composants ligne et diagonale satisfont la condition, mais la colonne ne satisfait pas la condition, donc le deuxième modèle Est la bonne réponse.
(Continu de gauche à droite)
12345
12345
12345
12345
12345
(Continu de droite à gauche)
15432
32154
54321
21543
43215
De plus, j'ai implémenté la matrice ci-dessus en notant que le dernier élément est +2 chacun.
B.py
n=int(input())
ans=[]
st=2
if n==1:exit(print(1))
for i in range(n):
now=[(st+i)%n if st+i!=n else n for i in range(n)][::-1]
st+=2
st%=n
if st==0:st=n
print(" ".join(map(str,now)))
Problème C
Il est relativement facile de voir ce que vous faites, mais vous devez faire attention à ne pas rechercher ** plusieurs fois **. Dans ce qui suit, la station est paraphrasée en haut.
Commencez par vérifier avec l'exemple suivant au début.
5 4 6
0 2 5 7 8
Par conséquent, en considérant les sous-ensembles connectés par des arêtes comme décrit ci-dessus, dans le cas d'un index inclus dans un certain sous-ensemble $ X $, la taille de $ X $ doit être calculée. En outre, vous pouvez considérer une collection de sous-ensembles mutuellement élémentaires qui ne sont pas connectés par des arêtes ** comme une famille d'ensemble élémentaire, et vous pouvez facilement les gérer à l'aide de l'arborescence ** Union Find **.
Ici, les sommets à unir dans l'arbre Union Find sont sélectionnés dans l'ordre à partir des sommets avec les coordonnées les plus petites, mais comme les sommets avec une distance de A ou plus et B ou moins peuvent être connectés, si les coordonnées des sommets sélectionnés sont maintenant $ C $, $ CB Vous pouvez sélectionner le sommet de $ ou plus et $ CA $ ou moins ou $ C + A $ ou plus et $ C + B $ ou moins. De plus, sélectionnez le côté à connecter ** parmi les sommets avec de petites coordonnées, et comme ce côté est bidirectionnel, vous pouvez sélectionner les sommets $ C + A $ ou plus et $ C + B $ ou moins.
De plus, cet appareil seul n'est pas bon en termes de montant de calcul. En effet, le pire calcul en sélectionnant un sommet entre $ C + A $ et $ C + B $ est $ O (N ^ 2 \ alpha (n)) $. $ \ Alpha (n) $ est l'inverse de la fonction Ackermann $ A (n, n) $ et semble être plus petit que $ \ log {n} $ (this slide Voir / union-find-49066733)).
Ici, afin de considérer les sommets recherchés, si les coordonnées des sommets que vous regardez sont $ C $ et les coordonnées des sommets que vous regardez juste avant sont $ C '$, le résultat sera comme indiqué dans la figure ci-dessous (** Dessinez un diagramme !! **).
À partir de la figure ci-dessus, suivez les sommets dans le sens des coordonnées décroissantes dans l'ordre à partir du plus grand sommet sous $ C + B $, et connectez les côtés. Vous pouvez rationaliser la recherche en utilisant la méthode de terminaison **. En conséquence, la plage de recherche n'est pas couverte, elle devient donc $ O (N \ alpha (n)) $ et un programme à grande vitesse peut être écrit. De plus, la taille de l'ensemble inclus dans la famille d'ensemble élémentaire à obtenir finalement peut être calculée par $ O (1) $ par la fonction taille.
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
//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
//Ci-dessous, l'ensemble premier et l'arbre représentent la même chose.
class UnionFind {
public:
vector<ll> parent; //parent[i]Est le parent de i
vector<ll> siz; //Un tableau représentant la taille de l'ensemble premier(Initialiser avec 1)
map<ll,vector<ll>> group;//Tableau associatif géré pour chaque ensemble premier(key est le parent de chaque ensemble premier, value est un tableau d'éléments de cet ensemble premier)
//Du constructeur:Initialiser les variables membres après
UnionFind(ll n):parent(n),siz(n,1){
//Initialement initialisé comme la racine de tous les éléments est lui-même
for(ll i=0;i<n;i++){parent[i]=i;}
}
ll root(ll x){ //Récupère la racine de l'arborescence à laquelle appartient la donnée x
if(parent[x]==x) return x;
return parent[x]=root(parent[x]);
//La valeur de l'expression d'affectation sera la valeur de la variable affectée
//Compression de chemin(Rationalisez les calculs en connectant les éléments directement à la racine)Il est réalisé
}
void unite(ll x,ll y){ //Fusionner les arbres x et y
ll rx=root(x);//La racine de x est rx
ll ry=root(y);//y root ry
if(rx==ry) return; //Quand dans le même arbre
//Fusionner un petit ensemble dans un grand ensemble(Fusionné de ry à rx)
if(siz[rx]<siz[ry]) swap(rx,ry);
siz[rx]+=siz[ry];
parent[ry]=rx; //Lorsque x et y ne sont pas dans le même arbre, attachez la racine y ry à la racine x rx
}
bool same(ll x,ll y){//Déterminez si l'arbre auquel appartiennent x et y est le même
ll rx=root(x);
ll ry=root(y);
return rx==ry;
}
ll size(ll x){ //Obtenez la taille de l'ensemble premier de x
return siz[root(x)];
}
//↓ Fonctions qui ne sont pas dans les bibliothèques d'autres personnes mais qui sont utiles
//O(n)Notez que
void grouping(ll n){//Ensembles élémentaires de groupe
REP(i,n){
if(group.find(parent[i])==group.end()){
group[parent[i]]={i};
}else{
group[parent[i]].PB(i);
}
}
}
};
signed main(){
//Code pour accélérer la saisie
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll n,a,b;cin>>n>>a>>b;
vector<ll> x(n);
REP(i,n)cin>>x[i];
UnionFind u(n);
//Ne vérifie pas trop
REP(i,n){
ll now=upper_bound(ALL(x),x[i]+b)-x.begin();now--;
//C'est ici?
//D'en haut
while(now>=0){
if(x[now]<x[i]+a)break;
if(u.same(i,now))break;
u.unite(i,now);
now--;
}
}
REP(i,n)cout<<u.size(i)<<endl;
}
Problème D
C'était un problème simple mais intéressant.
En vous concentrant sur la façon de faire une course, si les caractères avant et après ** sont différents lorsqu'une sous-colonne est sélectionnée, le nombre de courses augmentera de un. Par conséquent, j'ai pensé qu'il serait bon de sauvegarder ** ce qu'était le dernier caractère ** lors de la numérisation de la chaîne $ S $ depuis l'avant. De plus, il y a au plus 26 types de caractères (** état **) à la fin, et il semble que la transition lors de la numérisation puisse être facilement définie, j'ai donc décidé de la résoudre en utilisant DP.
Par conséquent, nous avons initialement défini DP comme suit:
$ dp [i] [j]: = $ (nombre d'exécutions lorsque le dernier alphabet est $ j $ (= 0 ~ 25) lorsque le caractère $ i $ est décidé)
Cependant, avec cette définition, l'ajout ne fonctionne pas lorsque l'on considère la transition de $ dp [i-1] $ à $ dp [i] $. Si vous examinez attentivement les informations nécessaires ici, vous constaterez que le nombre de chaînes de caractères ** lorsque vous décidez jusqu'au caractère ** $ i $ est nécessaire pour calculer le nombre d'exécutions. En d'autres termes, DP doit être défini comme suit.
$ dp [i] [j]: = $ (lorsque le dernier alphabet est $ j $ (= 0 ~ 25) lorsque le caractère $ i $ est décidé (nombre de chaînes de caractères, nombre d'exécutions))
Avec cette définition, la transition peut être implémentée en divisant le caractère $ i $ en trois cas: (1) en le sélectionnant comme premier caractère de la sous-chaîne, (2) en l'incluant dans la sous-chaîne, et (3) en ne l'incluant pas dans la sous-chaîne. Je peux le faire. Supposons également que l'alphabet du caractère $ i $ soit $ d $ et que le tableau de dp soit initialisé à 0.
(1) Lors de la sélection du caractère $ i $ comme premier caractère de la sous-chaîne
(2) Lorsque le caractère $ i $ n'est pas inclus dans la sous-colonne
(3) Lorsque le caractère $ i $ est inclus dans la sous-colonne
[1] Lorsque $ j = d $
(Le problème du sous-ensemble est que ** la transition est facile à comprendre si vous faites attention à savoir si vous sélectionnez l'élément ou non **, c'est donc l'un des DP auquel vous voulez vous habituer.)
De plus, cela trouvera la somme des exécutions de $ dp [n-1] $, mais si elle est laissée telle quelle, ce sera MLE. Par conséquent, comme la transition n'est que $ i-1 \ rightarrow i $, vous pouvez ** réduire la quantité de calcul spatial en ne sauvegardant que ces deux **.
D_MLE.py
s=input()
n=len(s)
#dp[i][j]:=Lorsque le i-ème caractère est décidé, il devient l'alphabet j(Nombre de chaînes de caractères,Nombre de courses)
#C'est rare de faire une paire, mais je ne peux pas décider si je ne sais pas non plus.
#Est devenu MLE
dp=[[[0,0] for i in range(26)] for i in range(n)]
mod=10**9+7
for i in range(n):
d=ord(s[i])-97
#Nouvellement ajouté
dp[i][d]=[1,1]
if i==0:continue
#Si tu ne choisis pas(N'augmentera pas)
for j in range(26):
dp[i][j][0]+=dp[i-1][j][0]
dp[i][j][0]%=mod
dp[i][j][1]+=dp[i-1][j][1]
dp[i][j][1]%=mod
#Lors du choix(S'il est différent, il augmentera du nombre de la chaîne de caractères)
for j in range(26):
if j==d:
dp[i][j][0]+=dp[i-1][j][0]
dp[i][j][0]%=mod
dp[i][j][1]+=dp[i-1][j][1]
dp[i][j][1]%=mod
else:
dp[i][d][0]+=dp[i-1][j][0]
dp[i][d][0]%=mod
dp[i][d][1]+=(dp[i-1][j][0]+dp[i-1][j][1])
dp[i][d][1]%=mod
ans=0
for j in range(26):
ans+=dp[n-1][j][1]
ans%=mod
print(ans)
D_AC.py
s=input()
n=len(s)
#dp[i][j]:=Lorsque le i-ème caractère est décidé, il devient l'alphabet j(Nombre de chaînes de caractères,Nombre de courses)
#C'est rare de faire une paire, mais je ne peux pas décider si je ne sais pas non plus.
#Est devenu MLE
#Ne faites pas de dp un tableau
x,y=[[0,0] for i in range(26)],[[0,0] for i in range(26)]
mod=10**9+7
for i in range(n):
d=ord(s[i])-97
#Nouvellement ajouté
if i==0:
x[d]=[1,1]
continue
#Si tu ne choisis pas(N'augmentera pas)
for j in range(26):
y[j][0]=x[j][0]
y[j][0]%=mod
y[j][1]=x[j][1]
y[j][1]%=mod
y[d][0]+=1
y[d][1]+=1
#Lors du choix(S'il est différent, il augmentera du nombre de la chaîne de caractères)
for j in range(26):
if j==d:
y[j][0]+=x[j][0]
y[j][0]%=mod
y[j][1]+=x[j][1]
y[j][1]%=mod
else:
y[d][0]+=x[j][0]
y[d][0]%=mod
y[d][1]+=(x[j][0]+x[j][1])
y[d][1]%=mod
x,y=y,x
ans=0
for j in range(26):
ans+=x[j][1]
ans%=mod
print(ans)
Après le problème E
Je ne résoudrai pas cette fois.
Recommended Posts