[PYTHON] Competitive professional devotion diary 15th to 17th days (7/9 to 7/11)

<!-Competitive professional devotion template->

Impressions

I'm sorry I couldn't solve ABC172-F Unfair Nim. Also, yesterday's ABC-class contest was a regrettable turn, so I'm disappointed. Recently, I've been frustrated with professional competition, but I want to grow on this basis.

Day 15

Solved ABC173-F Intervals on Tree. This article explains.

16th day

ABC136-E Max GCD

Time taken

About 40 minutes (20 minutes misread ...)

Consideration

I wanted to solve ABC172-F Unfair Nim, but I could finally understand it after seeing the explanation distribution and it seemed that it would take time to implement. So I'm thinking of solving it tomorrow. (Since it seems difficult to implement, I will skip it once.)

It's a blue diff, but I'm glad I was able to pass it. However, I misread it and used it for 20 minutes, so I want to be careful not to do it in the future.

I think it's a simple problem as long as you have an idea.

First, select $ (i, j) $ and add +1 to $ A_i $ and -1 to $ A_j $, but ** this operation does not change the sum ** (** invariant **) !) No. Furthermore, if the maximum value that can be divided after the operation is $ X $ and the value of the sequence at this time is $ C_i = X \ times B_i $, the following formula is established. (By the way, I misread that $ A_i $ has only +1.)

X \times B_1+X \times B_2+…+X \times B_n=A_1+A_2+…+A_n \leftrightarrow X\times (B_1+B_2+…+B_n)=A_1+A_2+…+A_n

In other words, $ X $ is a ** positive ** divisor of $ A_1 + A_2 +… + A_n $, so at most $ \ sqrt {n} $. Also, the minimum number of times (✳︎) for manipulating the sequence $ A $ for each $ X $ to change it to the sequence $ C $ should be less than $ k $. Here, in order to minimize the number of times, it is necessary to set $ X \ times B_i $ as close to $ A_i $ as possible (1) ** and ** the total number of times +1 and -1 appear. Must be equal (2) **.

According to (1), if any number is as close as possible to a multiple of $ X $ (** $ ceil (A_i / X) \ times X $ or $ floor (A_i / X) \ times X $ **) It is considered good, but this time, (2) is not satisfied when the pattern is as follows.

So, first, let's assume that each $ A_i $ is $ ceil (\ frac {A_i} {X}) \ times X $ (** It is important to assume and transform it for your convenience !) .. At this time, from $ A_i-ceil (\ frac {A_i} {X}) \ times X \ geqq 0 $, $ \ sum_ {i = 1} ^ {n} (A_i-ceil (\ frac {A_i} {X} ) \ times X) \ geqq 0 $. Also, since $ \ sum_ {i = 1} ^ {n} (A_i-B_i \ times X) = 0 $, $ \ sum_ {i = 1} ^ {n} (A_i-ceil (\ frac {A_i} { X}) \ times X)> If 0 $, $ ceil (\ frac {A_i} {X}) in $ A_i $ $ floor (\ frac {A_i} {X}) \ instead of \ times X $ It may be best to move to times X $. Furthermore, $ A_i-ceil (\ frac {A_i} {X}) \ times X -X = A_i-floor (\ frac {A_i} {X}) \ times X $ holds, so ** $ A_i-ceil ( $ A_i-ceil ( \ frac {A_i} {X}) \ times From the larger X $ to $ -X $ **… (1) and change to $ A_i-floor (\ frac {A_i} {X}) \ times X $ That $ \ sum_ {i = 1} ^ {n} (A_i-(ceil (\ frac {A_i} {X}) \ \ or \ \ floor (\ frac {A_i} {X})) \ times X) Do until = 0 $, and count the number of +1 (same as the number of -1) at that time is (✳︎), and (✳︎) is the largest $ X among $ k $ or less. Just ask for $.

(1)… $ A_i-ceil (\ frac {A_i} {X}) \ times It is intuitive and easy to show that the operation of $ -X $ from the one with the largest X $ is the best, so I will not show it here. (** Just show that the other options aren't optimal **, which is an important idea in greedy algorithm).

def make_divisors(n):
    divisors=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            divisors.append(i)
            if i!=n//i:
                divisors.append(n//i)
    #If you want to sort in descending order of divisors
    divisors.sort(reverse=True)
    return divisors
n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in make_divisors(sum(a)):
    x=[a[j]-(a[j]//i)*i for j in range(n)]
    x.sort(reverse=True)
    s=sum(x)
    compk=0
    for j in range(n):
        if s==0:
            break
        else:
            s-=i
            x[j]-=i
            compk+=abs(x[j])
    if compk<=k:
        print(i)
        break

Day 17

ABC137-E Coins Respawn

Time taken

1 hour 5 minutes

Consideration

It took me a long time to bug the library after I came up with the policy, but I think I will not bug it from now on because I have organized it a lot.

I was thinking about using BFS to follow, but ** it is clear that the result will change depending on how many sides you pass **, so ** use $ P $ coins when passing through each side. As **, I thought I would receive a $ C_i-P $ coin when passing through the $ i $ th side. Therefore, in the following, we will consider how many coins you can get at the maximum when moving from vertex $ 1 $ to vertex $ N $, assuming that you will receive coins of $ C_i-P $ on the $ i $ th side. ..

Here, if the sign of the coin obtained on each side is reversed and the coin is regarded as the distance, the distance of the $ i $ th side moves from the vertex $ 1 $ to the vertex $ N $ at $ P-C_i $. You can think of the shortest path problem (single starting point). Since $ P-C_i $ can be negative, we use the Bellman-Ford method (** reverse the sign and think about the minimum instead of the maximum ** pattern should be understood as a typical example).

Also, there may be a negative cycle ** in a graph with negative edge weights **, and in this problem the shortest path is ** when there is a negative cycle that includes the vertex $ N $ . It is not suitable because it is not fixed. Negative cycles are included in the graph if there are vertices whose shortest path is updated when the Bellman-Ford loop is turned extra. ( I will give you a summary article of the Bellman-Ford method soon **, so please refer to that as well.)

Here, I would like to show the existence of a negative cycle that includes the vertex $ N $, but there is a **-prone lie solution ** (hamayanhamayan's article. See .com / entry / 2019/08/14/131 217)). To avoid this lie-solving method, use BFS or DFS to trace the vertices that can be reached from the vertices where the shortest path is updated when the Bellman-Ford algorithm loop is turned once more * * (In my code, I do it in a function called bfs).

The solution obtained from the above is (1) When it is not possible to reach vertex N from vertex 1 → Output -1 (2) When the vertex 1 is reached to the vertex N and there is a negative cycle including the vertex $ N $ → -1 is output. (3) When it reaches from vertex 1 to vertex N and there is no negative cycle including vertex $ N $ → Output the larger of minus and 0 of the shortest distance It will be.

Similar

ABC061-D Score Attack My commentary article

//For compiler optimization
#pragma GCC optimize("O3")
//Include(Alphabetical order)
#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
//constant
#define INF 1000000000000 //10^12:Extremely large value,∞
#define MOD 1000000007 //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
#define Umap unordered_map
#define Uset unordered_set

struct Edge{
    ll to_Node;
    ll cost;
    Edge(ll t,ll c){to_Node=t;cost=c;}
};

vector<ll> mincost;
vector<vector<Edge>> Edges;
vector<bool> ncycle;
deque<ll> bfsrec;

//Negative cycle detection
void bfs(){
    ll s=SIZE(bfsrec);
    REP(i,s){
        ll now=*bfsrec.begin();
        bfsrec.pop_front();
        REP(i,SIZE(Edges[now])){
            if(ncycle[Edges[now][i].to_Node]==false){
                ncycle[Edges[now][i].to_Node]=true;
                bfsrec.PB(Edges[now][i].to_Node);
            }
        }
    }
    if(s)bfs();
}

bool bellmanford(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){
                            ncycle[Edges[j][k].to_Node]=true;//True if there is a negative cycle
                            bfsrec.PB(Edges[j][k].to_Node);
                        }
                    }
                }
            }
        }
    }
    bfs();
    if(ncycle[n-1]==true)return true;
    return false;//False if there is no negative cycle containing N
}


signed main(){
    //Code for speeding up input
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    ll n,m,p;cin>>n>>m>>p;
    mincost.resize(n);mincost[0]=0;
    FOR(i,1,n-1)mincost[i]=INF;
    Edges.resize(n);
    ncycle.resize(n);
    REP(i,n)ncycle[i]=false;
    //Minus the cost by p and reverse it
    REP(i,m){
        ll a,b,c;cin>>a>>b>>c;
        Edges[a-1].PB(Edge(b-1,p-c));
        //cout<<p-c<<endl;
    }
    //Consider the minimum under this
    bool check=bellmanford(n);
    if(check or mincost[n-1]==INF){
        cout<<-1<<endl;
    }else{
        cout<<max(-mincost[n-1],ll(0))<<endl;
    }
}