AtCoder Débutant Contest 168 Critique
Les résultats de cette fois
Le spectacle était de 1297.
Impressions de cette époque
Je pense que cela a fonctionné raisonnablement 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
Sortie séparément pour hon, bon et pon. Considérez simplement si c'est dans la liste.
A.py
n=input()
if int(n[-1]) in [2,4,5,7,9]:
print("hon")
elif int(n[-1]) in [3]:
print("bon")
else:
print("pon")
Problème B
Divisez le processus selon la longueur de k ou moins.
B.py
k=int(input())
s=input()
if len(s)<=k:
print(s)
else:
print(s[:k]+"...")
Problème C
(Quand j'ai fini de résoudre ce problème, j'étais satisfait des 300, mais j'ai obtenu un mauvais résultat à cause des problèmes D et E ...)
Dessinez la figure suivante et considérez l'angle par rapport à 12 heures.
Ensuite, le coin
Au fait, j'ai écrit un code court en Python, Ruby, Julia (tous sont les plus courts). Je n'ai pas beaucoup touché aux deux dernières langues, mais je pense que Julia est une langue intéressante, alors j'aimerais augmenter le nombre de CA.
C.py
import math
a,b,h,m=map(int,input().split())
q=abs((h+m/60)/12-m/60)*360
print(math.sqrt(a**2+b**2-2*a*b*math.cos(math.radians(q))))
C_shortest.py
from math import*;a,b,h,m=map(int,input().split());print((a*a+b*b-2*a*b*cos((m*11/360-h/6)*pi))**.5)
C_shortest.rb
include Math;a,b,h,m=gets.split.map &:to_f;p (a*a+b*b-2*a*b*cos((h/6-m*11/360)*PI))**0.5
C_shortest.jl
a,b,h,m=parse.(Int64,split(readline()));print((a^2+b^2-2a*b*cos(11π*m/360-h*π/6))^.5)
Problème D
Tout d'abord, quand j'ai vu le problème, j'ai pensé que c'était un Dyxtra car les restrictions semblaient strictes, mais dans ce problème la longueur de chaque itinéraire est la même, donc je devrais supposer que je le ferai avec BFS ou DFS avant Dixtra .. De plus, je n'ai jamais fait ce type de dikstra (sauf les pics à suivre), donc pendant le concours je l'ai résolu avec une sensation de différence d'eau inférieure.
Méthode Dyxtra (légèrement difficile)
Dyxtra trouve le ** chemin le plus court d'un seul point de départ **, mais si tous les côtés sont inversés, vous pouvez trouver le ** chemin le plus court d'un seul point final **. Dans ce problème, même si tous les côtés sont bidirectionnels et tous les côtés sont inversés, la combinaison des côtés sera la même, alors considérez le ** chemin le plus court du sommet 1 ** pour chaque sommet pour utiliser la méthode Dyxtra. Peut être utilisé. Aussi, puisque nous voulons trouver le numéro du sommet à aller au suivant en allant de chaque sommet au sommet 1 par le chemin le plus court **, si nous le considérons comme le chemin le plus court depuis le sommet 1, ** depuis le sommet 1 respectivement. Il peut être reformulé comme le numéro ** du sommet immédiatement précédent lorsque vous vous dirigez vers le sommet de.
Ici, la paraphrase ci-dessus peut être obtenue en considérant ** les informations des sommets susceptibles d'être atteints par la route la plus courte ** gérée par la file d'attente Priority dans la méthode Dyxtra avec ** où les sommets qui étaient devant elle **. Oui, il n'est pas difficile d'ajouter ** où se trouvait le sommet précédent ** lors de l'insertion d'informations sur ce sommet dans la file d'attente Priority (suivant [1] dans le code ci-dessous), donc dans le code ci-dessous Devenir.
De plus, lors de la gestion avec la file d'attente prioritaire, la paire était le type de cet élément, mais j'ai décidé de le changer en vecotor, qui est facile à développer.
D.cc
//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 10000007 //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
//À partir de là, un modèle
#define PLL pair<ll,ll>
#define VLL vector<ll>
//Plus grand par ordre croissant
//La comparaison des paires est la priorité du premier élément → le deuxième élément
#define PQ priority_queue<VLL,vector<VLL>,greater<VLL>>
//f est l'indice du point de départ
//n est le nombre total de sommets
//edge est un tableau avec l'index et la distance de la pointe de chaque bord pour le bord s'étendant à partir de ce bord.
//Enregistrez le précédent où vous êtes arrivé à la distance minimale de 1
pair<vector<ll>,vector<ll>> dijkstra(ll f,ll n,vector<vector<PLL>>& edge){
//Un tableau qui vérifie quels sommets ont été déterminés comme le chemin le plus court
vector<ll> confirm(n,false);
//Un tableau qui stocke la distance la plus courte à chaque sommet
//Le point de départ est 0,Initialisez la distance la plus courte avec INF sauf pour le point de départ
vector<ll> mincost(n,INF);mincost[f]=0;
//Un guide vers quel sommet aller(signpost)sauvegarder
vector<ll> signpost(n,-1);
//File d'attente prioritaire qui enregistre la distance depuis le point de départ des sommets qui s'étendent le long du côté s'étendant à partir de l'ensemble des sommets confirmés dans l'ordre croissant
//Enregistrez de quel sommet vous venez(Enregistrer l'itinéraire le plus court)
vector<ll> data={mincost[f],f,0};
//Puisqu'il y a trois éléments, utilisez vecteur au lieu de paire
PQ mincand;mincand.push(data);signpost[f]=0;
//Lorsque l'élément mincand est égal à zéro, cela indique qu'aucun sommet ne peut mettre à jour la distance la plus courte.
while(!mincand.empty()){
//Extraire le pic qui semble être atteint dans la distance la plus courte
VLL next=mincand.top();mincand.pop();
//Si la distance la plus courte au sommet a déjà été déterminée, sautez-la
if(confirm[next[1]]) continue;
//S'il n'est pas confirmé, faites-le confirmer
confirm[next[1]]=true;
//Lorsqu'elle est confirmée, la ligne directrice est également décidée
signpost[next[1]]=next[2];
//Obtenez des informations sur le côté s'étendant à partir de l'apex confirmé(La référence est plus rapide), L est le nombre de côtés
vector<PLL>& v=edge[next[1]];ll l=SIZE(v);
REP(i,l){
//Il n'est pas nécessaire de mettre à jour si la pointe du côté est confirmée((✳︎2)Est assez(✳︎1)Je n'en ai pas vraiment besoin)
if(confirm[v[i].F]) continue; //(✳︎1)
//Il n'est pas nécessaire de mettre à jour s'il est supérieur au coût minimum à la fin du côté(Satisfaire lorsque la pointe du côté est confirmée)
if(mincost[v[i].F]<=next[0]+v[i].S) continue; //(✳︎2)
//mise à jour
mincost[v[i].F]=next[0]+v[i].S;
//S'il est mis à jour, le sommet sera(Parmi les sommets non confirmés)Insérez dans le mincand car c'est peut-être la distance la plus courte
//Enregistrez également à partir de quel sommet pour atteindre le suivant
vector<ll> data_sub={mincost[v[i].F],v[i].F,next[1]};
mincand.push(data_sub);
}
}
return MP(mincost,signpost);
}
signed main(){
ll n,m;cin >> n >> m;
vector<vector<PLL>> edge(n);
REP(i,m){
ll a,b;cin >> a >> b;
edge[a-1].PB(MP(b-1,1));
edge[b-1].PB(MP(a-1,1));//Insérez le côté opposé
}
pair<vector<ll>,vector<ll>>vv=dijkstra(0,n,edge);
ll ans=0;
if(find(ALL(vv.S),-1)==(vv.S).end()){
cout << "Yes" << endl;
REP(i,n-1) cout << (vv.S)[i+1]+1 << endl;
}else{
cout << "No" << endl;
}
}
Méthode BFS (facile)
La méthode Dyxtra était une méthode que j'ai inventée pendant le concours, mais je l'ai remarquée lors de l'implémentation de la méthode Dyxtra. ** La longueur de chaque côté est égale **.
Par conséquent, on peut voir qu'il peut être recherché même avec un simple algorithme de recherche de graphe tel que ** BFS ou DFS ** (et cela est plus rapide avec une grande quantité de calcul O (N + M) et une quantité d'implémentation nettement inférieure). .. De plus, comme ces algorithmes traversent également les sommets les uns après les autres comme la méthode Dyxtra, ils ont la particularité ** qu'il est facile de sauvegarder les informations du sommet immédiatement précédent et du sommet courant **.
De plus, puisque nous considérons le chemin minimum cette fois, ** BFS **, qui stocke les sommets qui peuvent toujours être atteints à la même profondeur (distance), peut trouver le chemin minimum plus efficacement.
Fondamentalement, c'est la même chose que la méthode Dyxtra, et vous pouvez résoudre le problème en répétant le processus de traçage des choses que vous pouvez atteindre mais que vous n'avez pas visitées auparavant et en enregistrant le sommet précédent à ce moment-là.
De plus, en Python, ** limitez le nombre maximum de récurrences à être supérieur ou égal au nombre de récurrences **, et utilisez deque du module collections comme file d'attente qui peut être insérée et supprimée avec O (1) pour sauvegarder. besoin de le faire.
answerD.py
import sys
sys.setrecursionlimit(10**6)
from collections import deque
n,m=map(int,input().split())
path=[[] for i in range(n)]
for i in range(m):
a,b=map(int,input().split())
path[a-1].append(b-1)
path[b-1].append(a-1)
nan=deque([0])
check=[1 if i==0 else -1 for i in range(n)]
def bfs():
global n,m,path,nan
l=len(nan)
if not l:
return
for _ in range(l):
x=nan.popleft()
for j in path[x]:
if check[j]==-1:
check[j]=x
nan.append(j)
bfs()
bfs()
if any([i==-1 for i in check]):
print("No")
else:
print("Yes")
for i in range(1,n):
print(check[i]+1)
E problème
C'est un problème E que je ne pouvais pas résoudre et je me sentais frustré. Si cela est résolu, performances bleues ... Je ne pouvais pas penser à une méthode pour la dernière partie de comptage, et quand j'ai vu la réponse, il a dit ** Comptage de base ** et j'ai été choqué.
Tout d'abord, je veux trouver un ensemble de $ (i, j) $ (un ensemble de bad saury) qui satisfait cela en transformant la formule de $ A_i A_j + B_i B_j = 0 $, mais une telle formule est $ \ Lorsqu'il est transformé en frac {A_i} {B_i} = - \ frac {B_j} {A_j} $, ** le côté gauche ne dépend que de $ i $ et le côté droit ne dépend que de $ j $ **, donc $ ( Vous pouvez voir que i, j) $ devrait être éliminé. De plus, comme vous pouvez diviser par 0 à ce moment, vous pouvez voir que ** $ A_i, A_j, B_i, B_j $ doivent être considérés séparément si 0 est inclus **.
Tout d'abord, considérons le cas où $ A_i, A_j, B_i, B_j $ ne contient pas 0. Nous devons maintenant ** évaluer si les fractions sont égales pour la paire $ (i, j) $ qui est $ \ frac {A_i} {B_i} = - \ frac {B_j} {A_j} $. Donc, j'ai pensé qu'il serait bon d'évaluer ** si les paires de molécules et les dénominateurs sont égaux **.
Aussi,
Aussi, considérant la sardine $ i $ qui contient 0 dans $ A_i, B_i $, si $ A_i, B_i = 0,0 $, $ A_i A_j + B_i B_j = 0 avec n'importe quelle sardine. Puisque $ tient toujours, cela n'est possible que si vous choisissez une seule sardine. Dans le cas de $ A_i = 0, B_i \ neq0 $, ce n'est pas bon avec le calmar de $ B_i = 0, A_i \ neq0 $, donc le premier est $ A_i, B_i = 0,1 $ et $ A_i, B_i = 1,0 $ Si vous traitez comme, vous pouvez le gérer de la même manière que lorsque 0 n'est pas inclus dans $ A_i, A_j, B_i, B_j $.
Avec le traitement jusqu'à ce point, vous pouvez combiner saury avec $ (A_i, B_i) $ (tilt) qui peut être considéré comme identique. En dessous, m saury avec $ (A_i, B_i) $ et n saury avec $ (A_j, B_j) $ tel que $ A_i A_j + B_i B_j = 0 $ est valable (mauvaise relation) Considérez le nombre de façons de choisir ** parmi ** uniquement. C'est $ 2 ^ m + 2 ^ n-1 $. En effet, si vous choisissez ne serait-ce que l'un des m saury, vous ne pouvez pas choisir l'un des n saury, et vice versa. (Pendant le concours, je n'ai pas pu y penser à partir d'ici parce que je n'ai pas eu l'idée de prêter attention à ** combien de façons de choisir entre de mauvais amis **.)
Ici, ** si chaque balai peut être sélectionné ou non dépend uniquement du fait qu'un mauvais saury est sélectionné ou non **, on peut donc dire que ** il est déterminé indépendamment de la façon de sélectionner un autre balaur **. Par conséquent, une fois que le nombre de combinaisons entre les mauvais sammas ($ 2 ^ m + 2 ^ n-1 $ rues) est trouvé, il peut être multiplié par ** le nombre de combinaisons entre d'autres mauvais sammas **. Vous pouvez trouver la combinaison. De plus, si vous n'avez pas de mauvais ami, vous pouvez trouver le nombre de combinaisons sous la forme de $ 2 ^ k $ comme d'habitude.
** C'était un problème qui pouvait être résolu en remarquant la chose évidente si vous pensez qu'il est décidé indépendamment des sardines dont vous n'êtes pas proche. Je voudrais me connecter aux concours suivants et suivants pour ne pas oublier ce regret pour ne pas oublier une considération aussi naturelle.
answerE.py
#10**9+J'ai oublié 7 aussi
import math
n=int(input())
d=dict()
for i in range(n):
a,b=map(int,input().split())
if a==0 and b==0:
pass
elif a==0:
a,b=0,1
elif b==0:
a,b=1,0
else:
x=math.gcd(abs(a),abs(b))
a,b=a//x,b//x
if a<0:
a,b=-a,-b
if (a,b) in d:
d[(a,b)]+=1
else:
d[(a,b)]=1
#Comptez désormais
#print(d)
ans1,ans2=1,0
for i in d:
if d[i]==0:
continue
if i==(0,0):
ans2=d[i]
d[i]=0
continue
#L'indépendance ...
a,b=i
if (-b,a) in d:
ans1*=(2**(d[i])+2**(d[(-b,a)])-1)
d[(-b,a)]=0
d[i]=0
elif (b,-a) in d:
ans1*=(2**(d[i])+2**(d[(b,-a)])-1)
d[(b,-a)]=0
d[i]=0
else:
ans1*=(2**(d[i]))
d[i]=0
print((ans1+ans2-1)%(10**9+7))
Problème F
Il semble y avoir une méthode appelée compression de coordonnées, et quand j'entends le nom, je peux penser à un algorithme dans une certaine mesure, mais en raison de contraintes de temps, je vais l'ignorer. Je veux le résoudre dans un proche avenir.
Recommended Posts