AtCoder Beginner Contest 168 Review
This time's results
The performance was 1297.
Impressions of this time
I think it worked reasonably well this time. It was relatively easy to come up with because there were similar questions in the past in D and E. However, there were times when the implementation was buggy, so I want to avoid being impatient with such bugs. Also, I have considered the F problem properly at the very end, so I would like to be careful.
Problem A
Output separately for hon, bon, and pon. Just consider whether it is in the list.
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
The processing is divided according to the length of k or less.
B.py
k=int(input())
s=input()
if len(s)<=k:
print(s)
else:
print(s[:k]+"...")
C problem
(When I finished solving this problem, I was happy with the 300s, but I got a bad result due to the D and E problems, and the result was not so good ...)
Draw the following figure and consider the angle from the 12 o'clock direction.
Then, the angle
By the way, I wrote a short code in Python, Ruby, Julia (all are shortest). I haven't touched the last two languages so much, but I think Julia is an interesting language, so I'd like to increase the number of ACs.
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
First of all, I thought that it was Dijkstra because the restrictions seemed to be strict when I saw the problem, but since the length of each route is the same in this problem, I should assume that I will do it with BFS or DFS before Dijkstra. .. Moreover, I have never done this type of Dijkstra (save the vertices to follow), so during the contest I solved it with the feeling of being lower than the water diff.
Dijkstra's method (somewhat difficult)
Dijkstra finds the ** shortest path of a single start point **, but by reversing all sides, you can find the ** shortest path of a single end point **. In this problem, the combination of edges is the same even if all edges are bidirectional and all edges are reversed, so Dijkstra's algorithm can be used by considering the ** shortest path from vertex 1 ** for each vertex. Can be used. Also, since we want to find the number of the vertex to go to next when going from each vertex to vertex 1 by the shortest path **, if we consider it as the shortest path from vertex 1, ** from vertex 1 respectively. It can be rephrased as the number ** of the vertex that was immediately before when heading to the vertex of.
Here, the above paraphrase can be achieved by considering ** information of vertices that are likely to be reached by the shortest path ** managed by Priority queue in Dijkstra's algorithm together with ** where the vertex was before **. Yes, it's not difficult to add ** where the previous vertex was ** when inserting the vertex information into the Priority queue (next [1] in the code below), so in the code below Become.
Also, when managing with Priority queue, pair was the type of that element, but I decided to change it to vecotor, which is easy to expand.
D.cc
//Include(Alphabetical order,bits/stdc++.Factions that do not use h)
#include<algorithm>//sort,Binary search,Such
#include<bitset>//Fixed length bit set
#include<cmath>//pow,log etc.
#include<complex>//Complex number
#include<deque>//Queue for double-ended access
#include<functional>//sort greater
#include<iomanip>//setprecision(Floating point output error)
#include<iostream>//Input / output
#include<iterator>//Set arithmetic(Intersection,Union,Difference set, etc.)
#include<map>//map(dictionary)
#include<numeric>//iota(Generation of integer sequence),gcd and lcm(c++17)
#include<queue>//queue
#include<set>//set
#include<stack>//stack
#include<string>//String
#include<unordered_map>//Map with iterator but not keeping order
#include<unordered_set>//Set with iterator but not keeping order
#include<utility>//pair
#include<vector>//Variable length array
using namespace std;
typedef long long ll;
//macro
//for loop relationship
//The argument is(Variables in the loop,Range of movement)Or(Variables in the loop,First number,Number of ends)、のどちらOr
//If there is no D, the loop variable is incremented by 1, and if it is with D, the loop variable is decremented by 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 is a container such as vector
#define ALL(x) (x).begin(),(x).end() //I want to omit arguments such as sort
#define SIZE(x) ((ll)(x).size()) //size to size_Change from t to ll
#define MAX(x) *max_element(ALL(x)) //Find the maximum value
#define MIN(x) *min_element(ALL(x)) //Find the minimum value
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 10000007 //10^9+7:Congruence law
#define MAXR 100000 //10^5:The largest range in the array(Used for prime number enumeration etc.)
//Abbreviation
#define PB push_back //Insert into vector
#define MP make_pair //pair constructor
#define F first //The first element of pair
#define S second //The second element of pair
//Templates from here
#define PLL pair<ll,ll>
#define VLL vector<ll>
//Greater in ascending order
//Comparison of pairs is the priority of the first element → the second element
#define PQ priority_queue<VLL,vector<VLL>,greater<VLL>>
//f is the index of the starting point
//n is the total number of vertices
//edge is an array with the index and distance of the vertices beyond that edge for the edge extending from each vertex.
//Save the previous one at the minimum distance from 1
pair<vector<ll>,vector<ll>> dijkstra(ll f,ll n,vector<vector<PLL>>& edge){
//An array that checks which vertices have been determined as the shortest path
vector<ll> confirm(n,false);
//An array that stores the shortest distance to each vertex
//The starting point is 0,Initialize the shortest distance with INF except for the start point
vector<ll> mincost(n,INF);mincost[f]=0;
//Signpost of which apex to go to(signpost)Save
vector<ll> signpost(n,-1);
//Priority queue that saves the distance from the start point of the vertices that reach along the edge extending from the set of confirmed vertices in ascending order
//Save which vertex you came from(Saving the shortest path)
vector<ll> data={mincost[f],f,0};
//Since there are three elements, use vector instead of pair
PQ mincand;mincand.push(data);signpost[f]=0;
//When the mincand element is zero, it indicates that there are no vertices that can update the shortest distance.
while(!mincand.empty()){
//Take out the vertices that you think you can reach in the shortest distance
VLL next=mincand.top();mincand.pop();
//If the shortest distance to the apex has already been determined, skip it.
if(confirm[next[1]]) continue;
//If it is not confirmed, make it confirmed
confirm[next[1]]=true;
//When confirmed, the signpost is also decided
signpost[next[1]]=next[2];
//Get the information of the edge extending from the confirmed vertex(Reference is faster), L is the number of edges
vector<PLL>& v=edge[next[1]];ll l=SIZE(v);
REP(i,l){
//There is no need to update if the end of the side is confirmed((✳︎2)Is enough(✳︎1)I don't really need it)
if(confirm[v[i].F]) continue; //(✳︎1)
//There is no need to update if the mincost or more is above the edge(Satisfy when the tip of the side is confirmed)
if(mincost[v[i].F]<=next[0]+v[i].S) continue; //(✳︎2)
//update
mincost[v[i].F]=next[0]+v[i].S;
//If updated, the vertex will be(Among the unconfirmed vertices)Insert in mincand as it may be the shortest distance
//Save which vertex leads to the next one
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));//Insert the opposite side
}
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 method (easy)
Dijkstra's algorithm was a method I came up with during the contest, but I noticed it while implementing Dijkstra's algorithm. ** The length of each side is equal **.
Therefore, it can be seen that it is possible to search even with a simple graph search algorithm such as ** BFS or DFS ** (and this is faster with a computational complexity of O (N + M) and significantly less implementation). .. In addition, since these algorithms also pass through vertices one after another like Dijkstra's algorithm, they have the feature that ** it is easy to save information on the previous vertex and the current vertex **.
Also, since we consider the minimum path this time, ** BFS **, which stores vertices that can always be reached at the same depth (distance), can find the minimum path more efficiently.
It is basically the same as Dijkstra's algorithm, and you can solve the problem by repeating the steps that you can reach but have not visited before and save the vertex that was immediately before that time.
Also, in Python, ** limit the maximum number of recursion to be greater than or equal to the number of recursion possible **, and use deque of the collections module as a queue that can be inserted and deleted with O (1) to save. need to do it.
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
This is an E problem that I couldn't solve and felt frustrated. If this is solved, blue performance ... I couldn't think of a method for the last counting part, and when I saw the answer, it said ** Basic counting ** and I was shocked.
First, I want to find a set of $ (i, j) $ (a set of bad saury) that satisfies this by transforming the formula of $ A_i A_j + B_i B_j = 0 $, but such an equation is $ \ When transformed as frac {A_i} {B_i} =-\ frac {B_j} {A_j} $, ** the left side depends only on $ i $ and the right side depends only on $ j $ **, so $ ( You can see that the i, j) $ pair should be eliminated. Also, since you can divide by 0 at this time, you can see that ** $ A_i, A_j, B_i, B_j $ should be considered separately if 0 is included **.
First, consider the case where $ A_i, A_j, B_i, B_j $ does not contain 0. Now we need to ** evaluate if the fractions are equal for the $ (i, j) $ pair that is $ \ frac {A_i} {B_i} =-\ frac {B_j} {A_j} $. So, I thought it would be good to evaluate ** whether the numerator and denominator pairs are equal.
Also,
Also, considering the $ i $ sardine that contains 0 in $ A_i, B_i $, if $ A_i, B_i = 0,0 $, $ A_i A_j + B_i B_j = 0 with any sardine. Since $ always holds, it's only possible if you choose only one sardine. In the case of $ A_i = 0, B_i \ neq0 $, I have a bad relationship with the sardines of $ B_i = 0, A_i \ neq0 $, so the former is $ A_i, B_i = 0,1 $ and $ A_i, B_i = 1,0 $ If you process as, you can handle it in the same way as when 0 is not included in $ A_i, A_j, B_i, B_j $.
With the processing up to this point, saury with $ (A_i, B_i) $ (slope) that can be regarded as the same can be combined. Under this, m saury with $ (A_i, B_i) $ and n saury with $ (A_j, B_j) $ such that $ A_i A_j + B_i B_j = 0 $ hold (bad relationship) Consider how many ways to choose ** from ** only. This is $ 2 ^ m + 2 ^ n-1 $. This is because if you choose even one of the m saury, you cannot choose any n saury, and vice versa. (During the contest, I couldn't think about it from here because I didn't come up with the idea of paying attention to ** how many ways to choose between saury that are not close to each other **.)
Here, ** whether or not each saury can be selected depends only on whether or not a saury that is not close to each other is selected **, so it can be said that ** it is determined independently of how to select other saury **. Therefore, once the number of combinations between bad saury ($ 2 ^ m + 2 ^ n-1 $ streets) is found, it is ** multiplied by the number of combinations between other bad saury **. You can find the combination. Also, if you don't have a bad saury, you can find the number of combinations in the form of $ 2 ^ k $ as usual.
** It was a problem that could be solved if you noticed something that was natural when you thought that it was decided independently of the sardines that you didn't get along with. I would like to connect to the next and subsequent contests so as not to forget this regret so as not to forget such a natural consideration.
answerE.py
#10**9+I forgot about 7 too
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
#Count from now on
#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
#Independence ...
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
There seems to be a method called coordinate compression, and when I hear the name, I can think of an algorithm to some extent, but due to time constraints, I will skip it. I want to solve it in the near future.
Recommended Posts