concours yukicoder 261 avis

résultat

スクリーンショット 2020-08-15 11.06.22.png

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

IMG_0544.PNG

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 !! **).

IMG_23DFFB46C036-1.jpeg

À 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 dp[i][d][0]+=1 dp[i][d][1]+=1

(2) Lorsque le caractère $ i $ n'est pas inclus dans la sous-colonne dp[i][j][0]+=dp[i-1][j][0] dp[i][j][1]+=dp[i-1][j][1]

(3) Lorsque le caractère $ i $ est inclus dans la sous-colonne [1] Lorsque $ j = d $ dp[i][d][0]+=dp[i-1][j][0] dp[i][d][1]+=dp[i-1][j][1] [2] Quand $ j \ neq d $ (l'exécution augmente du montant de la chaîne de caractères) dp[i][d][0]+=dp[i-1][j][0] dp[i][d][1]+=(dp[i-1][j][0]+dp[i-1][j][1])

(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

concours yukicoder 259 avis
concours yukicoder 264 avis
concours yukicoder 261 avis
concours yukicoder 267 avis
concours yukicoder 266 avis
concours yukicoder 263 avis
yukicoder contest 268 avis
Critique du concours AtCoder Beginner Contest 152
AtCoder Grand Contest 041 Critique
yukicoder contest 265 Record de participation
Revue du concours régulier AtCoder 105
concours yukicoder 266 Record de participation
concours yukicoder 243 Record de participation
record de 256 entrées
yukicoder contest 273 Record de participation
Critique du concours AtCoder Débutant 160
Critique du concours AtCoder Débutant 178
AtCoder Débutant Contest 167 Évaluation
concours yukicoder 252 Record de participation
concours yukicoder 259 Record de participation
Critique du concours AtCoder
concours yukicoder 249 Record de participation
AtCoder Débutant Contest 169 Évaluation
concours yukicoder 271 Record de participation
AtCoder Grand Contest 048 Critique
record de participation au concours 267 de yukicoder
Critique du concours AtCoder Débutant 181
Concours yukicoder 251 Record de participation
AtCoder Débutant Contest 171 Critique
Critique du concours AtCoder pour débutant 182
yukicoder contest 242 Record de participation
Critique du concours AtCoder Débutant 180
concours yukicoder 241 Record de participation
Critique du concours AtCoder pour débutant 177
record du concours 264 de yukicoder
AtCoder Débutant Contest 168 Critique
AtCoder Grand Contest 045 Critique
Revue du concours de programmation NOMURA 2020
AtCoder Grand Contest 044 Critique
yukicoder contest 245 record d'inscription
yukicoder contest 257 Record de participation
record de participation au concours yukicoder 250
Concours yukicoder 254 Record de participation
Critique du concours AtCoder
Critique du concours AtCoder pour débutant 172
AtCoder Regular Contest 106 Évaluation
yukicoder contest 246 Record de participation
concours yukicoder 275 Record de participation
Concours yukicoder 274 Record de participation
Critique du concours AtCoder
concours yukicoder 247 Record de participation
AtCoder Grand Contest 046 Critique
AtCoder Débutant Contest 175 Critique
Examen du concours de programmation HHKB 2020
Critique du concours AtCoder
Critique du concours AtCoder Beginner Contest 153
Critique du concours AtCoder pour débutant 156
AtCoder Débutant Contest 161 Critique
yukicoder contest 261 Record de participation
AtCoder Débutant Contest 170 Critique