[PYTHON] AtCoder Beginner Contest 164 Review
This time's results
Impressions of this time
Problem A
Cases are classified according to whether w is s or more.
A.py
s,w=map(int,input().split())
print("unsafe" if w>=s else "safe")
B problem
Aoki's physical strength becomes c → cb due to Takahashi's attack, and Takahashi's physical strength becomes a → ad than Aoki's attack, so since the restrictions are loose, the physical strength becomes 0 or less first by simulating the attack. The one who loses. The check saves which attack turn.
B.py
a,b,c,d=map(int,input().split())
check=True
while True:
if check:
c-=b
if c<=0:
print("Yes")
break
else:
a-=d
if a<=0:
print("No")
break
check=not check
C problem
This is a common pattern. There are several ways without a cover, so use set.
C.py
n=int(input())
s=set()
for i in range(n):
s.add(input())
print(len(s))
D problem
If you get stuck in D even for a moment, you will end up with a failure like this ... ** You need to have a firm grasp of typical problems **.
First, looking at the sample, I noticed that ** there are few patterns **, and if I honestly write out all the strings from i to j, it is clear that O ($ N ^ 2 $) is not enough ** You can see that there is.
Based on this, when considering the number $ n $ from the $ i $ character to the $ j $ character, ** "the number from the $ i $ character to the last character ($ k
answerD.py
s=input()
l=len(s)
se=dict()
k=0
for i in range(l-1,-1,-1):
k+=(pow(10,l-1-i,2019)*int(s[i]))
k%=2019
if k in se:
se[k]+=1
else:
se[k]=1
ans=0
for j in se:
i=se[j]
if i>1:
ans+=(i*(i-1)//2)
if j==0:
ans+=i
print(ans)
E problem
It's a problem with Dijkstra's algorithm (I noticed Dijkstra's algorithm, but I couldn't solve it in time ...). Even the implementation of the basic Dijkstra method was suspicious, so I have given it as a summary of the Dijkstra method in Another article along with an explanation of this problem. Please be in when it is good reference. For the time being, I will paste only the code below.
answerE.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
//The size of this INF is also important(If it is small, it will be WA)
#define INF 1000000000000000 //10^15: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 VL vector<ll>
//Greater in ascending order
//Vector comparison is the priority of the first element, the second element ...
#define PQ priority_queue<VL,vector<VL>,greater<VL>>
//Maximum number of silver coins to have
#define MAXS ll(2999)
//f is the index of the starting point
//n is the total number of vertices
//s is the number of currencies you have first
//edge is the index and decrease of the vertices beyond that edge for the edge extending from each vertex(or increase)An array with the number of silver coins and the time it takes
vector<VL> dijkstra(ll f,ll n,ll s,vector<vector<VL>>& edge){
//The maximum number of silver coins you have is MAXS
s=min(s,MAXS);
//An array that checks whether the shortest time in the state of the number of currencies of each vertex has been determined
vector<VL> confirm(n,VL(MAXS+1,false));
//An array that stores the shortest time in the state of the number of each currency at each vertex
//Initial state at the starting point(I have S currency)Is 0, otherwise INF initializes the shortest time
vector<VL> mincost(n,VL(MAXS+1,INF));mincost[f][s]=0;
//Confirmed(vertex,Number of currencies)Along the side that extends from the set of(vertex,Number of currencies)Priority queue that saves the time taken from the initial state of
PQ mincand;mincand.push({mincost[f][s],f,s});
//The shortest time can be updated when the mincand element is zero(vertex,Number of currencies)Indicates that there is no state of
while(!mincand.empty()){
//It seems to reach the shortest distance(vertex,Number of currencies)Take out the state of
VL next=mincand.top();mincand.pop();
//Already that(vertex,Number of currencies)If the shortest time in the state of is confirmed, skip it
if(confirm[next[1]][next[2]]) continue;
//If it is not confirmed, make it confirmed
confirm[next[1]][next[2]]=true;
//Confirmed(vertex,Number of currencies)The information of the side extending from the state of is fetched, l is the number of the side
vector<VL>& v=edge[next[1]];ll l=SIZE(v);
REP(i,l){
//Calculate how many silver coins will be after moving. If it exceeds MAXS, set it to MAXS.
ll nextS=min(next[2]+v[i][1],MAXS);
//Cannot move if the number of silver coins after moving is less than 0
if(nextS<0) continue;
//There is no need to update if the time when moving is longer than the mincost at the end of the side(Satisfy this when the tip of the side is confirmed)
if(mincost[v[i][0]][nextS]<=next[0]+v[i][2]) continue;
//update
mincost[v[i][0]][nextS]=next[0]+v[i][2];
//If updated, that(vertex,Number of currencies)The state of(Not confirmed(vertex,Number of currencies)In the state of)Can be the shortest distance
mincand.push({mincost[v[i][0]][nextS],v[i][0],nextS});
}
}
return mincost;
}
signed main(){
ll n,m,s;cin >> n >> m >> s;
vector<vector<VL>> edge(n);
REP(i,m){
ll u,v,a,b;cin >> u >> v >> a >> b;
//Here the sides are bidirectional
edge[u-1].PB({v-1,-a,b});
edge[v-1].PB({u-1,-a,b});
}
REP(i,n){
ll c,d;cin >> c >> d;
//Add the operation to increase the currency as an edge
edge[i].PB({i,c,d});
}
vector<VL> mincost=dijkstra(0,n,s,edge);
FOR(i,1,n-1) cout << MIN(mincost[i]) << endl;
}
F problem
I was tired from the effort of one article due to the E problem, so I will solve it at another time.
Recommended Posts