torus711 のアレ

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

強連結成分分解

AtCoder Beginner Contest 335, E : Non-Decreasing Colorful Path

問題文 https://atcoder.jp/contests/abc335/tasks/abc335_e 問題概要 $n$ 頂点 $m $ 辺からなる連結な単純無向グラフ $G = ( V, E )$ があり,$i$ 番目の辺は頂点 $V_i$ と $U_i$ を双方向に結んでいる.また,整数列 $A = \langle A_1, A_2, \dots, A_n \r…

AtCoder Beginner Contest 245, F : Endless Walk

問題文 https://atcoder.jp/contests/abc245/tasks/abc245_f 問題概要 単純有向グラフ $G = ( V, E )$ が与えられる. 頂点 $v \in V$ であって,$v$ を始点として $G$ 上で無限に(辺に沿った)移動を繰り返すことができるものの個数を求めよ. 制約 $1 \le…

TopCoder SRM 628, Division 2, Level 3 : InvariantSets

問題文 http://community.topcoder.com/stat?c=problem_statement&pm=13242&rd=16009 問題概要 内の整数からなる集合 と、 上の写像 がある。 は配列 によって表され、 である。 また、 の部分集合 が invariant set であるとは、次の条件を満たすときである…