問題 問題概要 N頂点M辺の距離のある無向グラフが与えられる. 頂点S,TからA,Bが各々頂点T,Sに最短路で向かうとき,AとBがすれ違わないような組み合わせをmod 1e9+7で求めよ. 1 <= N <= 105, 1 <= M <= 2*105, 1 <= d <= 109 解法 問題の流れ : Dijkstra -> DP…

問題 問題概要 N個の整数 {a_i} (i=1,2,..,N) が与えられる. 各 i = 1,2,..,N について min_(1<=j<=N) (a_j + (j-i)2) を求めよ. 1 <= N <= 2*105, 1 <= a_i <= 1012 解法 a_j + (j-i)2 = i2 + (-2ji + j2 + a_j) より, 各iについて, (-2ji + j2 + a_j)を最…