# [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.

### Similar

C ++ code

#### abc137e.cc


//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;
}
}