[PYTHON] AtCoder Beginner Contest 126 Revue des questions précédentes

Les résultats de cette fois

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.

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.

À 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>

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)

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])