[PYTHON] AtCoder Beginner Contest 061 Review of past questions
Time required
Problem A
Just output in different cases
answerA.py
a,b,c=map(int,input().split())
if a<=c<=b:
print("Yes")
else:
print("No")
answerA_better.py
a,b,c=map(int,input().split())
print("Yes" if a<=c<=b else "No")
B problem
Just count the number of each city
answerB.py
n,m=map(int,input().split())
x=[0]*n
for i in range(m):
y,z=map(int,input().split())
x[y-1]+=1
x[z-1]+=1
for i in range(n):
print(x[i])
C problem
It ’s really a big growth to be able to kill these problems in seconds. It's ridiculous to think about each insertion, so if you think about what it will look like in the end, you'll know that you should finally sort in ascending order and start with the smallest one. Therefore, I realize that I should think about how many elements there are from 1 to 10 ** 5, so prepare an array to count each element. If you can prepare it, you can see that the count is counted from the front and the element when it becomes k or more is the K-th smallest number.
answerC.py
n,k=map(int,input().split())
x=[0]*(10**5)#1~10**5
for i in range(n):
a,b=map(int,input().split())
x[a-1]+=b
for i in range(10**5):
k-=x[i]
if k<=0:
print(i+1)
break
D problem
It's a blue level problem, but I was able to solve it in about 30 minutes! (I have also issued 4WA, so I regret it.) The policy itself was set up relatively quickly, but I couldn't finish the details. First of all, there is a suspicion that it is the Bellman-Ford method because the weights of the edges are positive and negative in the overt weighted directed graph and it seems that we can go even if we look at the constraints. However, since it is a problem to find the longest path instead of the shortest path, the weights can be reversed, and this can be achieved by multiplying the weights of all sides by -1 (** If you consider the longest path instead of the shortest path). I got the finding that it can be reversed by multiplying by -1. I think it can be used for other problems as well. ). Basically, you can do it this way ( Don't forget to multiply by -1 in the final output **), but you need to think about the case of inf. At first, I used the Bellman-Ford algorithm's negative cycle judgment condition without thinking about anything, but in some cases it became WA. If you think about it carefully here, even if a negative cycle is created in a place unrelated to the path taken when reaching the Nth vertex, the negative cycle will be detected, so the Nth vertex is included. You can see that we need to detect a negative cycle.
When I was writing this article, I was reading Kenchon's article and found that it was a lie. I would like to rewrite it to the correct solution and repost it in another article. The part with the strikethrough below is a lie, so think about it while referring to Kenchon's article. Please give me.
The Bellman-Ford code was written in a university class, so the first code is to use that code (the Node structure manages all the information). Also, since int will overflow, set it to long long and set the INF value to a sufficiently large value. By turning the loop (number of vertices-1) times in this state (if there is no negative cycle, the shortest path from one vertex to another passes through at most N vertices once (number of vertices). -1) You can find such a route enough in 1), and the shortest route can be found. Then, if the shortest path to the vertex N is updated when the loop is turned once more, it can be determined that there is a negative cycle including the vertex N. ~~ Also, when I made a code (second code) when the Node structure is not used, the constant speedup was successful and I was able to shorten it from 47ms to 8ms.
answerD.cc
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
//You have to do enough here
#define INF 1000000000000
struct Node{
//Node information
vector<pair<ll,ll>> edge;//Node number and cost to connect to each edge
//Bellman-Ford algorithm data
ll mincost=INF;//Minimum cost to that node
};
//Remove unrelated loops
bool bellmanford(vector<Node>& nodes,ll l1){
//(l1-1)(Ordinary bellman)+1(detection)
for(ll i=0;i<l1;i++){
for(ll j=0;j<l1;j++){
Node x=nodes[j];
if(x.mincost!=INF){
ll l2=x.edge.size();
for(ll k=0;k<l2;k++){
ll a=x.mincost+x.edge[k].second;
if(nodes[x.edge[k].first].mincost>a){
nodes[x.edge[k].first].mincost=a;
if(i==l1-1 and x.edge[k].first==l1-1) return true;//True if there is a negative cycle
}
}
}
}
}
return false;//False if there is no negative cycle
}
int main(){
ll n,m;cin >> n >> m;
vector<Node> Nodes(n);
//Only update mincost0 firmly
Nodes[0].mincost=0;
for(ll i=0;i<m;i++){
ll a,b,c;cin >> a >> b >> c;
Nodes[a-1].edge.push_back(make_pair(b-1,-c));
}
//Update Nodes
if(bellmanford(Nodes,n)){
cout << "inf" << endl;
}else{
cout << -Nodes[n-1].mincost << endl;
}
}
answer.cc
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
using namespace std;
typedef long long ll;
//You have to do enough here
#define INF 1000000000000
struct Edge{
ll to_Node;
ll cost;
Edge(ll t,ll c){to_Node=t;cost=c;}
};
//Remove unrelated loops
bool bellmanford(vector< vector<Edge> >& Edges,vector<ll>& mincost,ll n){
//(l1-1)(Ordinary bellman)+1(detection)
for(ll i=0;i<n;i++){
for(ll j=0;j<n;j++){
if(mincost[j]!=INF){
ll e=Edges[j].size();
for(ll k=0;k<e;k++){
ll new_mincost=mincost[j]+Edges[j][k].cost;
if(mincost[Edges[j][k].to_Node]>new_mincost){
mincost[Edges[j][k].to_Node]=new_mincost;
if(i==n-1 and Edges[j][k].to_Node==n-1)return true;//True if there is a negative cycle
}
}
}
}
}
return false;//False if there is no negative cycle
}
int main(){
ll n,m;cin >> n >> m;
vector<ll> mincost(n,INF);
vector< vector<Edge> > Edges(n);
//Only update mincost0 firmly
mincost[0]=0;
for(ll i=0;i<m;i++){
ll a,b,c;cin >> a >> b >> c;
Edges[a-1].push_back(Edge(b-1,-c));
}
//Update Nodes
if(bellmanford(Edges,mincost,n)){
cout << "inf" << endl;
}else{
cout << -mincost[n-1] << endl;
}
}
Recommended Posts