[PYTHON] AtCoder Anfängerwettbewerb 168 Bewertung
Die Ergebnisse dieser Zeit
Die Leistung war 1297.
Eindrücke dieser Zeit
Ich denke, diesmal hat es einigermaßen gut funktioniert. Es war relativ einfach, sich etwas auszudenken, da es in der Vergangenheit in D und E ähnliche Fragen gab. Es gab jedoch Zeiten, in denen die Implementierung fehlerhaft war, daher möchte ich vermeiden, mit solchen Fehlern ungeduldig zu sein. Außerdem habe ich das F-Problem ganz am Ende richtig betrachtet, daher möchte ich vorsichtig sein.
Problem A
Separate Ausgabe für hon, bon und pon. Überlegen Sie einfach, ob es in der Liste ist.
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")
B-Problem
Teilen Sie den Prozess nach der Länge von k oder weniger.
B.py
k=int(input())
s=input()
if len(s)<=k:
print(s)
else:
print(s[:k]+"...")
C-Problem
(Als ich mit der Lösung dieses Problems fertig war, war ich mit den 300ern zufrieden, bekam aber aufgrund der D- und E-Probleme ein schlechtes Ergebnis ...)
Zeichnen Sie die folgende Abbildung und betrachten Sie den Winkel aus der 12-Uhr-Richtung.
Dann die Ecke
Übrigens habe ich Kurzcode in Python, Ruby, Julia geschrieben (alle sind am kürzesten). Ich habe die letzten beiden Sprachen nicht so sehr berührt, aber ich denke, Julia ist eine interessante Sprache, deshalb möchte ich die Anzahl der ACs erhöhen.
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)
D Problem
Als ich das Problem sah, dachte ich zunächst, dass es sich um ein Dyxtra handelt, da die Einschränkungen streng zu sein schienen, aber bei diesem Problem ist die Länge jeder Route gleich, daher sollte ich davon ausgehen, dass ich es mit BFS oder DFS vor Dyxtra tun werde. .. Außerdem habe ich diese Art von Dikstra noch nie gemacht (außer den zu verfolgenden Gipfeln), also habe ich sie während des Wettbewerbs mit einem Gefühl von geringerem Wasserdiff gelöst.
Dyxtra-Methode (etwas schwierig)
Dyxtra findet den ** kürzesten Weg eines einzelnen Startpunkts **, aber wenn alle Seiten umgekehrt sind, können Sie den ** kürzesten Weg eines einzelnen Endpunkts ** finden. Selbst wenn in diesem Problem alle Seiten bidirektional und alle Seiten umgekehrt sind, ist die Kombination der Seiten dieselbe. Berücksichtigen Sie daher den ** kürzesten Pfad von Scheitelpunkt 1 ** für jeden Scheitelpunkt, um die Dyxtra-Methode zu verwenden. Kann verwendet werden. Da wir die Nummer des Scheitelpunkts ermitteln möchten, zu dem als nächstes übergegangen werden soll, wenn von jedem Scheitelpunkt zum Scheitelpunkt 1 über den kürzesten Pfad ** gewechselt wird, gilt dies als der kürzeste Pfad von Scheitelpunkt 1 bzw. ** von Scheitelpunkt 1. Sie kann als Nummer ** des unmittelbar vorhergehenden Scheitelpunkts umformuliert werden, wenn Sie zum Scheitelpunkt von gehen.
Hier kann die obige Paraphrase erreicht werden, indem ** die Informationen der Scheitelpunkte berücksichtigt werden, die wahrscheinlich auf dem kürzesten Weg erreicht werden **, der von der Prioritätswarteschlange in der Dyxtra-Methode verwaltet wird, zusammen mit ** den Scheitelpunkten, die davor lagen **. Ja, es ist nicht schwierig, ** hinzuzufügen, wo der vorherige Scheitelpunkt war **, wenn Informationen zu diesem Scheitelpunkt in die Prioritätswarteschlange eingefügt werden (nächste [1] im folgenden Code), also im folgenden Code Werden.
Bei der Verwaltung mit der Prioritätswarteschlange war das Paar der Typ dieses Elements, aber ich habe beschlossen, es in vecotor zu ändern, was leicht zu erweitern ist.
D.cc
//Einschließen(Alphabetischer Reihenfolge,bits/stdc++.Eine Fraktion, die h nicht benutzt)
#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<iterator>//Betrieb einstellen(Produktset,Summensatz,Differenzsatz etc.)
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge
using namespace std;
typedef long long ll;
//Makro
//für Schleifenbeziehung
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Enden)、のどちらOder
//Schleifenvariablen ohne D werden um 1 erhöht, und Schleifenvariablen mit D werden um 1 dekrementiert.
#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 ist ein Container wie ein Vektor
#define ALL(x) (x).begin(),(x).end() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach ll
#define MAX(x) *max_element(ALL(x)) //Finden Sie den Maximalwert
#define MIN(x) *min_element(ALL(x)) //Finden Sie den Mindestwert
//Konstante
#define INF 1000000000000 //10^12:Extrem großer Wert,∞
#define MOD 10000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays(Wird für die Aufzählung von Primzahlen usw. verwendet.)
//Abkürzung
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
//Ab hier ist eine Vorlage
#define PLL pair<ll,ll>
#define VLL vector<ll>
//Größer in aufsteigender Reihenfolge
//Der Vergleich von Paaren ist die Priorität des ersten Elements → des zweiten Elements
#define PQ priority_queue<VLL,vector<VLL>,greater<VLL>>
//f ist der Index des Startpunktes
//n ist die Gesamtzahl der Eckpunkte
//Kante ist ein Array mit dem Index und dem Abstand der Spitze jeder Kante für die Kante, die sich von dieser Kante erstreckt.
//Speichern Sie die vorherige, in der Sie angekommen sind, in der Mindestentfernung von 1
pair<vector<ll>,vector<ll>> dijkstra(ll f,ll n,vector<vector<PLL>>& edge){
//Ein Array, das prüft, welche Scheitelpunkte als kürzester Pfad ermittelt wurden
vector<ll> confirm(n,false);
//Ein Array, das den kürzesten Abstand zu jedem Scheitelpunkt speichert
//Der Startpunkt ist 0,Initialisieren Sie die kürzeste Entfernung mit INF mit Ausnahme des Startpunkts
vector<ll> mincost(n,INF);mincost[f]=0;
//Eine Anleitung, zu welchem Gipfel man gehen soll(signpost)sparen
vector<ll> signpost(n,-1);
//Prioritätswarteschlange, die den Abstand vom Startpunkt der Scheitelpunkte speichert, die entlang der Seite reichen, die sich vom Satz bestätigter Scheitelpunkte in aufsteigender Reihenfolge erstreckt
//Speichern Sie, von welchem Scheitelpunkt Sie gekommen sind(Den kürzesten Weg speichern)
vector<ll> data={mincost[f],f,0};
//Da es drei Elemente gibt, verwenden Sie den Vektor anstelle des Paares
PQ mincand;mincand.push(data);signpost[f]=0;
//Wenn das Mincand-Element Null ist, zeigt dies an, dass es keinen Scheitelpunkt gibt, der die kürzeste Entfernung aktualisieren kann.
while(!mincand.empty()){
//Extrahieren Sie den Gipfel, der in kürzester Entfernung erreicht zu sein scheint
VLL next=mincand.top();mincand.pop();
//Wenn der kürzeste Abstand zum Scheitelpunkt bereits ermittelt wurde, überspringen Sie ihn
if(confirm[next[1]]) continue;
//Wenn es nicht bestätigt wird, machen Sie es bestätigt
confirm[next[1]]=true;
//Wenn dies bestätigt ist, wird auch die Richtlinie festgelegt
signpost[next[1]]=next[2];
//Informieren Sie sich über die Seite, die sich vom bestätigten Scheitelpunkt aus erstreckt(Referenz ist schneller), L ist die Anzahl der Seiten
vector<PLL>& v=edge[next[1]];ll l=SIZE(v);
REP(i,l){
//Es ist keine Aktualisierung erforderlich, wenn die Spitze der Seite bestätigt wird((✳︎2)Reicht(✳︎1)Ich brauche es nicht wirklich)
if(confirm[v[i].F]) continue; //(✳︎1)
//Es ist keine Aktualisierung erforderlich, wenn die Mindestkosten am Ende der Seite überschritten werden(Zufrieden sein, wenn die Spitze der Seite bestätigt ist)
if(mincost[v[i].F]<=next[0]+v[i].S) continue; //(✳︎2)
//aktualisieren
mincost[v[i].F]=next[0]+v[i].S;
//Wenn aktualisiert, wird der Scheitelpunkt sein(Unter den unbestätigten Eckpunkten)In Mincand einlegen, da dies die kürzeste Entfernung sein kann
//Speichern Sie auch, von welchem Scheitelpunkt aus der nächste erreicht werden soll
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));//Setzen Sie die gegenüberliegende Seite ein
}
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;
}
}
BFS-Methode (einfach)
Die Dyxtra-Methode war eine Methode, die ich während des Wettbewerbs entwickelt habe, aber ich habe sie bei der Implementierung der Dyxtra-Methode bemerkt. ** Die Länge jeder Seite ist gleich **.
Daher ist ersichtlich, dass es sogar mit einem einfachen Graphsuchalgorithmus wie ** BFS oder DFS ** durchsucht werden kann (und dies ist schneller mit einem großen Rechenaufwand O (N + M) und einem wesentlich geringeren Implementierungsaufwand). .. Da diese Algorithmen wie die Dyxtra-Methode auch nacheinander die Scheitelpunkte durchlaufen, haben sie außerdem die Eigenschaft, dass ** es einfach ist, die Informationen des unmittelbar vorhergehenden Scheitelpunkts und des aktuellen Scheitelpunkts zu speichern **.
Da wir diesmal die Mindestroute berücksichtigen, kann ** BFS **, das die Eckpunkte speichert, die immer in derselben Tiefe (Entfernung) erreicht werden können, die Mindestroute effizienter finden.
Es ist im Grunde dasselbe wie die Dyxtra-Methode, und Sie können das Problem lösen, indem Sie den Vorgang des Verfolgens der Dinge wiederholen, die Sie erreichen können, aber noch nicht besucht haben, und die Scheitelpunkte speichern, die unmittelbar vor dieser Zeit lagen.
Beschränken Sie in Python ** die maximale Anzahl von Wiederholungen auf mindestens die Anzahl der Wiederholungen ** und verwenden Sie deque des Sammlungsmoduls als Warteschlange, die zum Speichern mit O (1) eingefügt und gelöscht werden kann. müssen es tun.
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 Problem
Dies ist ein E-Problem, das ich nicht lösen konnte und das ich frustriert fühlte. Wenn dies gelöst ist, blaue Leistung ... Ich konnte mir keine Methode für den letzten Zählteil vorstellen, und als ich die Antwort sah, stand dort ** Grundzählung ** und ich war schockiert.
Zuerst möchte ich eine Menge von $ (i, j) $ (eine Menge von schlechtem Saury) finden, die dies erfüllt, indem sie die Formel von $ A_i A_j + B_i B_j = 0 $ transformiert, aber eine solche Gleichung ist $ \ Bei der Transformation als frac {A_i} {B_i} = - \ frac {B_j} {A_j} $ hängt ** die linke Seite nur von $ i $ und die rechte Seite nur von $ j $ ** ab, also $ ( Sie können sehen, dass i, j) $ eliminiert werden sollte. Da Sie zu diesem Zeitpunkt durch 0 teilen können, können Sie sehen, dass ** $ A_i, A_j, B_i, B_j $ separat betrachtet werden sollten, wenn 0 enthalten ist **.
Betrachten Sie zunächst den Fall, in dem $ A_i, A_j, B_i, B_j $ keine 0 enthält. Jetzt müssen wir ** bewerten, ob die Brüche für das $ (i, j) $ -Paar gleich sind, das $ \ frac {A_i} {B_i} = - \ frac {B_j} {A_j} $ ist. Daher dachte ich, es wäre gut zu bewerten, ob die Paare von Molekülen und Nennern gleich sind.
Ebenfalls,
Berücksichtigt man auch die $ i $ Sardine, die 0 in $ A_i, B_i $ enthält, wenn $ A_i, B_i = 0,0 $, $ A_i A_j + B_i B_j = 0 mit einer beliebigen Sardine. Da $ immer gilt, ist es nur möglich, wenn Sie nur eine Sardine auswählen. Im Fall von $ A_i = 0, B_i \ neq0 $ ist es nicht gut mit dem Tintenfisch von $ B_i = 0, A_i \ neq0 $, also ist der erstere $ A_i, B_i = 0,1 $ und $ A_i, B_i = 1,0 $ Wenn Sie als verarbeiten, können Sie genauso damit umgehen, als wenn 0 nicht in $ A_i, A_j, B_i, B_j $ enthalten ist.
Mit der Verarbeitung bis zu diesem Punkt können Sie Saury mit $ (A_i, B_i) $ (Tilt) kombinieren, das als gleich angesehen werden kann. Darunter gilt m saury mit $ (A_i, B_i) $ und n saury mit $ (A_j, B_j) $, so dass $ A_i A_j + B_i B_j = 0 $ gilt (schlechte Beziehung) Überlegen Sie, wie viele Möglichkeiten Sie nur ** auswählen können. Dies ist $ 2 ^ m + 2 ^ n-1 $. Dies liegt daran, dass Sie, wenn Sie auch nur einen der m saury wählen, keinen der n saury wählen können und umgekehrt. (Während des Wettbewerbs konnte ich von hier aus nicht darüber nachdenken, weil ich nicht auf die Idee gekommen war, darauf zu achten, wie viele Möglichkeiten es gibt, zwischen schlechten Freunden zu wählen.)
Hier hängt die Frage, ob jeder Saury ausgewählt werden kann oder nicht, nur davon ab, ob ein schlechter Saury ausgewählt ist oder nicht. Es kann also gesagt werden, dass ** unabhängig davon bestimmt wird, wie ein anderer Saury ausgewählt wird **. Sobald die Anzahl der Kombinationen zwischen schlechten Sammas ($ 2 ^ m + 2 ^ n-1 $ Straßen) gefunden ist, kann sie daher mit ** der Anzahl der Kombinationen zwischen anderen schlechten Sammas ** multipliziert werden. Sie finden die Kombination. Wenn Sie keinen schlechten Freund haben, können Sie die Anzahl der Kombinationen wie gewohnt in Form von $ 2 ^ k $ finden.
** Es war ein Problem, das gelöst werden konnte, wenn Sie etwas Natürliches bemerkten, als Sie dachten, dass es unabhängig von den Sardinen entschieden wurde, mit denen Sie nicht klar kamen. Ich möchte mich mit dem nächsten und den folgenden Wettbewerben verbinden, um dieses Bedauern nicht zu vergessen und eine so natürliche Überlegung nicht zu vergessen.
answerE.py
#10**9+Ich habe auch 7 vergessen
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
#Von nun an zählen
#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
#Unabhängigkeit ...
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))
F Problem
Es scheint eine Methode namens Koordinatenkomprimierung zu geben, und wenn ich den Namen höre, kann ich mir bis zu einem gewissen Grad einen Algorithmus vorstellen, aber aus Zeitgründen werde ich ihn überspringen. Ich möchte es in naher Zukunft lösen.
Recommended Posts