AtCoder Beginner Contest 164 Review

This time's results

スクリーンショット 2020-04-26 23.13.50.png

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 )" to "" I remembered that there was a ** similar problem that I thought by subtracting the number from the j-1 $ character to the last character ($ l $) ", so I thought that it could be used here as well. In other words, to find out if the number $ n $ from the $ i $ character to the $ j $ character is a multiple of 2019, if ** $ k, l $ are coprime when 2019 is the law. It can be said that (i, j) satisfies the condition ** (∵ ** 2019 is relatively prime with 2 and 5 **). Therefore,xNumber from the first letter to the last letter|S|Store the number of remainders divided by 2019 for each street in the dictionary, and when each remainder z has y streets_yC_2so(i,j)の組み合わせを求めることがsoきます。このzを0~2018so考えて和を考えれば良いのsoすが、ここso二つ罠があります。 The first trap is that this method doesn't consider whether the number from the ** $ i $ character to the last character is a multiple of 2019 **. Therefore, we need to add the elements such that z is 0 as the answer. The second trap, as you can see in the code below, is that you have to calculate the power of 10 with the pow function when first calculating the number from the $ x $ character to the last character. However, the exponent of ** 10 is 200,000-1 at the maximum, so it takes a long time to calculate pow **. Therefore, here, you can calculate the power with a small amount of calculation by introducing the condition that ** mod is 2019 and calculating ** (mod can be specified as the third argument in Python). With this speedup, TLE can be taken, and it is possible to write a program with sufficient execution time.

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

AtCoder Beginner Contest 152 Review
AtCoder Beginner Contest 160 Review
AtCoder Beginner Contest 178 Review
AtCoder Beginner Contest 166 Review
AtCoder Beginner Contest 167 Review
AtCoder Beginner Contest 164 Review
AtCoder Beginner Contest 169 Review
AtCoder Beginner Contest 181 Review
AtCoder Beginner Contest 171 Review
AtCoder Beginner Contest 182 Review
AtCoder Beginner Contest 180 Review
AtCoder Beginner Contest 177 Review
AtCoder Beginner Contest 168 Review
AtCoder Beginner Contest 179 Review
AtCoder Beginner Contest 172 Review
AtCoder Beginner Contest 176 Review
AtCoder Beginner Contest 175 Review
AtCoder Beginner Contest 174 Review
AtCoder Beginner Contest 153 Review
AtCoder Beginner Contest 156 Review
AtCoder Beginner Contest 161 Review
AtCoder Beginner Contest 170 Review
AtCoder Beginner Contest 165 Review
AtCoder Beginner Contest 173 Review
AtCoder Beginner Contest 155 Review
AtCoder Beginner Contest 162 Review
AtCoder Beginner Contest 177
AtCoder Beginner Contest 179
AtCoder Beginner Contest 172
AtCoder Beginner Contest 180
AtCoder Beginner Contest 173
Atcoder Beginner Contest 153
AtCoder Beginner Contest 066 Review past questions
AtCoder Beginner Contest 181 Note
AtCoder Grand Contest 041 Review
AtCoder Regular Contest 105 Review
AtCoder Beginner Contest 187 Note
AtCoder Beginner Contest 180 Note
AtCoder Beginner Contest 182 Note
AtCoder Grand Contest 048 Review
AtCoder Beginner Contest 156 WriteUp
AtCoder Grand Contest 045 Review
AtCoder Grand Contest 044 Review
Solve AtCoder Beginner Contest 100-102
AtCoder Beginner Contest 167 Memorandum
AtCoder Beginner Contest 183 Note
AtCoder Regular Contest 106 Review
AtCoder Beginner Contest 184 Note
AtCoder Grand Contest 046 Review
AtCoder Regular Contest 104 Review
AtCoder Beginner Contest 188 Note
AtCoder Beginner Contest 102 Review of past questions
AtCoder Beginner Contest 072 Review of past questions
AtCoder Beginner Contest 085 Review of past questions
AtCoder Beginner Contest 062 Review of past questions
AtCoder Beginner Contest 051 Review of past questions
AtCoder Beginner Contest 127 Review of past questions
AtCoder Beginner Contest 119 Review of past questions
AtCoder Beginner Contest 151 Review of past questions
AtCoder Beginner Contest 075 Review of past questions
AtCoder Beginner Contest 110 Review of past questions