Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

AOJ 2345 : Network Reliability

AOJ 動的計画法グラフ数学

問題文 : Network Reliability | Aizu Online Judge

概要

無向グラフ $G = (V, E)$ と整数 $p$ が与えられる． $G$ の各枝が独立に $p$ パーセントの確率で消失するとき，グラフが連結である確率を求めよ．

制約

$1 \leq |V| \leq 14$
$0 \leq |E| \leq 100$

続きを読む

AOJ 1178: A Broken Door

問題文 : A Broken Door | Aizu Online Judge

概要

日本語なので略。

続きを読む

AOJ 1341: Longest Chain

問題文 : Longest Chain | Aizu Online Judge

概要

$\mathbb{Z}^3$ に半順序関係 $\prec$ を

$(x_1, y_1, z_1) \prec (x_2, y_2, z_2) \overset{\triangle{}}{\Leftrightarrow} x_1 < x_2$ かつ $y_1 < y_2$ かつ $z_1 < z_2$

で導入する。 $n$ 個の $\mathbb{Z}^3$ の点の中で、上記で定めた半順序を満たす最長の列の長さを求めよ。

制約
- $1 \leqq n \leqq 3 \times 10^5$

続きを読む