AtCoder Beginner Contest 126 Revue des questions précédentes

Les résultats de cette fois

スクリーンショット 2020-06-05 0.45.33.png

Impressions de cette époque

A partir d'aujourd'hui, pour le moment, je voudrais passer à ABC (6 questions) après 126. Personnellement, je pense que le problème est devenu plus sophistiqué ces jours-ci, alors assurez-vous de le porter. Je voudrais le joindre. De plus, cette fois, j'ai pu le terminer complètement. J'ai passé le problème F sans beaucoup de preuves, donc je voudrais le revoir fermement.

Problème A

J'ai oublié la fonction de conversion en minuscules, j'ai donc divisé les cas par A, B ou C. De plus, c'est la fonction inférieure qui se convertit en minuscules, ce qui vous permet d'écrire du beau code (le deuxième code). N'est-ce pas difficile pour un problème?

A.py


n,k=map(int,input().split())
s=input()
if s[k-1]=="A":
    print(s[:k-1]+"a"+s[k:])
elif s[k-1]=="B":
    print(s[:k-1]+"b"+s[k:])
else:
    print(s[:k-1]+"c"+s[k:])

A_shorter.py


n,k=map(int,input().split())
s=input()
print(s[:k-1]+s[k-1].lower()+s[k:])

Problème B

Le mois possible (MM) est 00-12, alors gardez ceci comme candidat pour le mois (cand)

B.py


s=input()
cand={"0"+str(i) if i<10 else str(i) for i in range(1,13)}
if s[:2] in cand and s[2:] in cand:
    print("AMBIGUOUS")
elif s[:2] in cand:
    print("MMYY")
elif s[2:] in cand:
    print("YYMM")
else:
    print("NA")

Problème C

J'ai pensé prendre le plafond de log, mais je l'ai évité cette fois car il y a une erreur dans la fraction. Le seul moyen pour Sunuke de gagner est de se présenter jusqu'à ce qu'il soit ** K ou supérieur ** (car si vous le retournez $ \ parce que $, ce sera 0 et vous perdrez). Par conséquent, il suffit de compter le nombre de fois jusqu'à ce qu'il devienne K ou plus, mais comme la valeur des premiers dés peut être de 1 à N, la solution peut être trouvée par $ O (N \ log N) $.

C.py


n,k=map(int,input().split())
ans=0
for i in range(1,n+1):
    j,now=0,i
    while now<k:
        j+=1
        now*=2
    ans+=(2**(-j))
print(ans/n)

Problème D

Ce n'est pas parce que c'est un arbre que vous devez être prêt, vous devez donc être calme. Sous les contraintes de ce problème, il y a toujours ** une manière de peindre qui rencontre le sujet. Maintenant, concentrons-nous sur un certain pic. A ce moment, on peut dire que les sommets connectés aux sommets sont ** de la même couleur si la longueur du côté reliant les deux sommets est paire, et de couleurs différentes ** si la longueur est impaire. Cela peut être dit à n'importe quel sommet, donc si vous décidez correctement du point de départ et que vous le suivez avec une recherche de priorité de profondeur, vous pouvez trouver la solution avec $ O (M + N) $.

(Le but est de le mettre dans la simple question de ** ce qui se passe à un certain pic **.)

answerD.py


import sys
sys.setrecursionlimit(10**6)
n=int(input())
path=[[] for i in range(n)]
for i in range(n-1):
    u,v,w=map(int,input().split())
    path[u-1].append((v-1,w%2))
    path[v-1].append((u-1,w%2))
ans=[0]+[-1]*(n-1)
def dfs(i):
    global n,path,ans
    for j in path[i]:
        if ans[j[0]]==-1:
            if j[1]:
                ans[j[0]]=1-ans[i]
                dfs(j[0])
            else:
                ans[j[0]]=ans[i]
                dfs(j[0])
dfs(0)
print("\n".join(map(str,ans)))

E problème

C'est beaucoup plus facile à résoudre car il dit qu'il n'y a pas de contradiction dans les conditions données. De plus, comme il n'y a que deux types de chaque carte, je considérerai d'abord la ** recherche complète **, mais je rejetterai cette politique car c'est évidemment impossible.

Ici, il suffit de déterminer si $ A_ {x_i} + A_ {y_i} + Z_i $ est pair, et comme $ Z_i $ est connu, l'un des ** $ A_ {x_i} $ et $ A_ {y_i} $ est Si vous le savez, l'autre sera définitivement décidé **. On voit donc que le numéro de chaque carte est ** déterminé dans une chaîne par les informations connues $ A_ {x_i} + A_ {y_i} + Z_i $ **, donc ** les cartes déterminées dans une chaîne sont du même ensemble. Vous pouvez utiliser Union Find Tree (forêt élémentaire d'ensemble) pour gérer en tant que **. Bien sûr, vous pouvez penser à $ A_ {x_i} + A_ {y_i} + Z_i $ comme unissant $ A_ {x_i} $ et $ A_ {y_i} $.

Aussi, je veux savoir combien d'ensembles premiers il y a dans la ** forêt d'ensembles premiers, donc après avoir utilisé la fonction de regroupement dans Union Find Library Trouvez simplement la taille du groupe.

La mise en œuvre de ceci ressemble à ceci:

De plus, ** combien d'ensembles élémentaires sont dans la forêt ** est, en termes généraux, ** des composants connectés (le plus grand des graphes partiels où il y a un chemin entre deux sommets quelconques). C'est la même valeur que le nombre **, et s'écrit dans cette solution comme cette dernière.

E.cc


//Comprendre(Ordre alphabétique)
#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 1000000007 //10^9+7:Droit commun
#define MAXR 100000 //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

//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éterminer 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,m;cin >> n >> m;
    UnionFind uf(n);
    REP(i,m){
        ll x,y,z;cin >> x >> y >> z;
        uf.unite(x-1,y-1);
    }
    REP(i,n)uf.root(i);
    uf.grouping(n);
    cout << SIZE(uf.group) << endl;
}

Problème F

J'ai fait un modèle pratique et donné une réponse appropriée, donc Answer et [le blog d'ARMERIA](https: // betrue12. Je l'ai examiné en référence à hateblo.jp/entry/2019/05/20/213302). (Cependant, je pense qu'il n'y a pas beaucoup de gens qui ca font des preuves pendant le concours ...?)

Tout d'abord, c'était un problème de $ xor $, j'ai donc décidé d'en décider un pour chaque bit, mais ** j'ai remarqué qu'il y avait trop de motifs et j'ai abandonné ** (si ce n'est pas possible, abandonnez une fois!).

Alors ensuite, j'ai décidé de ** me concentrer sur deux des mêmes entiers **. Ici, ** $ xor $ entre les mêmes entiers devient $ 0 $ **, donc si vous les arrangez pour qu'ils soient appariés les uns aux autres comme indiqué dans la figure ci-dessous, $ xor $ de $ a_i $ à $ a_j $ changera. C'est égal à $ x ou $ de $ a_ {i + 1} $ à $ a_ {j-1} $, et j'ai pensé que ce serait pratique.

IMG_0398.JPG

De plus, quand $ j-i + 1 $ est même ici, tous les entiers peuvent être regroupés pour faire le $ x ou $ 0 $ entier, donc quand $ K $ est $ 0 $, Construisez comme indiqué ci-dessus avec $ i = 1, j = 2 ^ {M + 1} $.

Je l'ai soumis parce que je pensais qu'il n'y avait que ce modèle, donc il est devenu WA, mais lorsque je ** change et continue à considérer **, j'ai trouvé qu'il y avait aussi un modèle où $ j-i + 1 $ devenait étrange comme le montre la figure ci-dessous. J'ai fait.

IMG_0400.JPG

À ce stade, en insérant $ K $ entre les deux, comme indiqué dans la figure ci-dessus, il est possible de créer une paire qui satisfait les conditions pour des entiers autres que $ K $ (puisqu'elle est prise en sandwich entre eux, ** $ K $ vaut 0 $ ou plus. Doit être inférieur à 2 $ ^ M $ **.). Ce modèle existe également si le XOR de tous les entiers autres que $ K $ inclus dans la partie entre $ K $ est calculé et devient $ K $.

De plus, il était difficile de penser qu'il existait autre chose que ce motif à symétrie élevée (** ← trop grossier **), j'ai donc pu AC lorsque je l'ai mis à -1 sauf pour les deux motifs ci-dessus. En fait, il peut être prouvé qu'il n'y a pas d'autre modèle, donc il est montré ci-dessous.

<détails>

Preuve </ summary>

Jusqu'à ce qui précède, nous avons montré qu'il existe une séquence de nombres qui satisfait la condition lorsque $ k = 0 $ ((1)) (le modèle de la première figure).

Ici, "Quand $ 0 \ leqq K <2 ^ M $, $ xor $ obtenu en soustrayant $ K $ du nombre de $ 0 $ ou plus et moins de $ 2 ^ M $ devient $ K $. "Exists" (②) est affiché en premier (le modèle dans la deuxième figure), puis il n'y a pas de séquence de nombres qui satisfait la condition lorsque $ k \ geqq 2 ^ M $ (③).


Ici, en utilisant que ** $ xor $ de deux entiers consécutifs $ 2a, 2a + 1 $ ($ a $ est un entier) devient 1, ** le nombre entier de $ 0 $ ou plus et moins de $ 2 ^ M $ Pour $ x ou $ de $ M \ geqq 2 $, vous pouvez créer un nombre pair de paires de deux entiers consécutifs $ 2a, 2a + 1 $ ($ a $ est un entier) **. Par conséquent, le total $ xor $ est $ 0 $ car il y a un nombre pair de paires où $ xor $ est $ 1 $ ($ \ car $$ xor $ théorème d'addition).

De plus, lorsque le total $ xor $ du nombre de $ 0 $ ou plus et inférieur à 2 $ ^ M $ est de 0 $, $ xor $ excluant $ K $ devient $ K $ **, donc ($ \ parce que $$) On montre que le modèle ci-dessus est valable pour K \ xor \ K = 0 $) et $ M \ geqq 2 $.

De plus, lorsque $ M = 0 $ et $ M = 1 $, le nombre de ** total $ xor $ qui est supérieur ou égal à 0 $ $ et inférieur à 2 $ ^ M $ n'est pas 0 $, donc $ xor $ excluant $ K $ est Cela ne devient pas $ K $, et même si vous écrivez des cas possibles, vous ne pouvez pas créer une séquence de nombres qui remplit les conditions.

Par conséquent, ② a été affiché.


De plus, dans le cas de $ k \ geqq 2 ^ m $, certains bits sont $ M $ ou plus et deviennent 1, mais le nombre de $ 0 $ ou plus et inférieur à $ 2 ^ M $ est de $ M $ ou plus. Il n'y a rien qui devient 1, donc cela n'existe pas non plus dans ce cas. Par conséquent, ③ a été affiché.

À partir de (1), (2) et (3) ci-dessus, vous pouvez montrer que votre solution est nécessaire et suffisante.

F.py


from itertools import chain
m,k=map(int,input().split())
if k==0:
    print(" ".join([str(i) for i in chain(range(0,2**m),range(2**m-1,-1,-1))]))
elif 0<k<2**m:
    s=0
    for i in range(0,2**m):
        if i!=k:
            s^=i
    if s==k:
        print(" ".join([str(i) for i in chain(range(0,k),range(k+1,2**m),[k],range(2**m-1,k,-1),range(k-1,-1,-1),[k])]))
    else:
        print(-1)
else:
    print(-1)

F_shortest.py


m,k=map(int,input().split());x=list(range(2**m));print(*x[::-1]+x if k<1 else x[:k:-1]+x[k-1::-1]+[k]+x[:k]+x[k+1:]+[k]if(k<2**m)&(m>1)else[-1])

Recommended Posts

AtCoder Beginner Contest 102 Revue des questions précédentes
AtCoder Beginner Contest 085 Revue des questions précédentes
AtCoder Beginner Contest 062 Revue des questions précédentes
AtCoder Beginner Contest 113 Revue des questions précédentes
AtCoder Beginner Contest 074 Revue des questions précédentes
AtCoder Beginner Contest 051 Revue des questions précédentes
AtCoder Beginner Contest 119 Revue des questions précédentes
AtCoder Beginner Contest 151 Revue des questions précédentes
AtCoder Beginner Contest 075 Revue des questions précédentes
AtCoder Beginner Contest 054 Revue des questions précédentes
AtCoder Beginner Contest 110 Revue des questions précédentes
AtCoder Beginner Contest 117 Revue des questions précédentes
AtCoder Beginner Contest 070 Revue des questions précédentes
AtCoder Beginner Contest 105 Revue des questions précédentes
AtCoder Beginner Contest 112 Revue des questions précédentes
AtCoder Beginner Contest 076 Revue des questions précédentes
AtCoder Beginner Contest 089 Revue des questions précédentes
AtCoder Beginner Contest 069 Revue des questions précédentes
AtCoder Beginner Contest 079 Revue des questions précédentes
AtCoder Beginner Contest 056 Revue des questions précédentes
AtCoder Beginner Contest 087 Revue des questions précédentes
AtCoder Beginner Contest 093 Revue des questions précédentes
AtCoder Beginner Contest 046 Revue des questions précédentes
AtCoder Beginner Contest 123 Revue des questions précédentes
AtCoder Beginner Contest 049 Revue des questions précédentes
AtCoder Beginner Contest 078 Revue des questions précédentes
AtCoder Beginner Contest 047 Revue des questions précédentes
AtCoder Beginner Contest 104 Revue des questions précédentes
AtCoder Beginner Contest 057 Revue des questions précédentes
AtCoder Beginner Contest 121 Revue des questions précédentes
AtCoder Beginner Contest 126 Revue des questions précédentes
AtCoder Beginner Contest 090 Revue des questions précédentes
AtCoder Beginner Contest 103 Revue des questions précédentes
AtCoder Beginner Contest 061 Revue des questions précédentes
AtCoder Beginner Contest 059 Revue des questions précédentes
AtCoder Beginner Contest 044 Revue des questions précédentes
AtCoder Beginner Contest 083 Revue des questions précédentes
AtCoder Beginner Contest 048 Revue des questions précédentes
AtCoder Beginner Contest 124 Revue des questions précédentes
AtCoder Beginner Contest 116 Revue des questions précédentes
AtCoder Beginner Contest 097 Revue des questions précédentes
AtCoder Beginner Contest 088 Revue des questions précédentes
AtCoder Beginner Contest 092 Revue des questions précédentes
AtCoder Beginner Contest 099 Revue des questions précédentes
AtCoder Beginner Contest 065 Revue des questions précédentes
AtCoder Beginner Contest 053 Revue des questions précédentes
AtCoder Beginner Contest 094 Revue des questions précédentes
AtCoder Beginner Contest 063 Revue des questions précédentes
AtCoder Beginner Contest 107 Revue des questions précédentes
AtCoder Beginner Contest 071 Revue des questions précédentes
AtCoder Beginner Contest 064 Revue des questions précédentes
AtCoder Beginner Contest 082 Revue des questions précédentes
AtCoder Beginner Contest 084 Revue des questions précédentes
AtCoder Beginner Contest 068 Revue des questions précédentes
AtCoder Beginner Contest 058 Revue des questions précédentes
AtCoder Beginner Contest 043 Revue des questions précédentes
AtCoder Beginner Contest 098 Revue des questions précédentes
AtCoder Beginner Contest 114 Revue des questions précédentes
AtCoder Beginner Contest 045 Revue des questions précédentes
AtCoder Beginner Contest 120 Revue des questions précédentes
AtCoder Beginner Contest 108 Revue des questions précédentes