torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

Warshall-Floyd 法

Good Bye 2014, B : New Year Permutation

問題文 http://codeforces.com/contest/500/problem/B 問題概要 サイズ の順列 及び, 行列 が与えられる.また, 及び が成り立つ. 二つの整数 について, であるときに限り, と を交換することができる.任意回の操作で作ることができる列の内,辞書式順…

TopCoder, SRM 622, Division 1, Level 1 : BuildingRoutes

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13193&rd=15855 問題概要 有向重み付き完全グラフ G = ( V, E ) と、正整数 T が与えられる。全ての頂点対 ( s, t ) について、s -> t の最短路を考える(ある ( s, t ) に対し最短路が複…

TopCoder SRM 608, Division 2, Level 3 : BigOEasy

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13002&rd=15841 問題概要 有向グラフ が与えられる。このグラフ上の長さ L の歩道について考える。L が大きくなったとき、歩道の数のオーダーを L の多項式で表せるか求めよ。表せる場合…

TopCoder SRM 584, Division 1, Level 1 ( Division 2, Level 2 ) : Egalitarianism

概要 N 人の市民がいて、それぞれの友達関係が与えられる。 友達同士であるような二人の市民について、その所持金の差が d 以内になるようにしたとき、任意の二人の市民(友達同士でなくてもよい)の所持金の差の最大値はいくらになるか求めよ。 解が無限大…

TopCoder SRM 581, Division 1, Level 2 : TreeUnion

概要 V 個の頂点から成る二つの木 T1, T2 が与えられ、この二つを V 本の辺で結ぶ。 より詳しくは次の手順で辺を張る。 0 ? V - 1 の順列をランダムに一つ選び P とする 各 i ( 0 このとき、相異なる K ( 3