主食は米

主に競プロ備忘録

2018-02-17から1日間の記事一覧

Educational Codeforces Round 38 D. Buy a Ticket

問題 問題概要 N頂点M辺の無向グラフと各辺の距離が与えられる. また各頂点に対してコストc[i]が与えられる. 各i (1<=i<=N)に対し min_j(2dist(i, j)+c(j))を求めよ. 2 <= N <= 2105, 1 <= M <= 2*105 解法 Dijkstraで各頂点とそのコストを初期位置としてキ…

Educational Codeforces Round 38 C. Constructing Tests

問題 問題概要 0,1からなる行列で,どのMxMの小行列をとってもいずれかの要素に0が含まれる行列をM-free Matrixという. 整数xが与えられ,1の要素数を最大化したNxNのM-free Matrixで,1の要素数がxであるようなN,Mを答えよ. というクエリがt個与えられるので各…