競技プログラミングにおけるグラフ理論・組合せ数学・動的計画法の応用テクニック
弦なし閉路の検出と辺グラフ変換
長さ4以上の弦なし閉路を検出する問題では、頂点ベースの探索ではなく辺をノードとする線グラフへの変換が有効である。有向辺 $(u \to v)$ と $(v \to w)$ の間に、辺 $(u, w)$ が存在しない場合にのみ有向辺を張る。この変換により、元のグラフにおける三角形は新グラフで閉路を形成しなくなる。新グラフ上でDFSを実行し、最も深い返祖辺 ...
9月14日 12:35 投稿
確率と最適化問題の解法
サイコロとコイン
n面ダイスとコインを使用するゲームの勝率を求める。初期値としてダイスを振り、値が1～K-1の場合コインを繰り返し振る。表が出れば値が倍増、裏が出れば0になり、0で敗北またはK以上で勝利となる。
解法
初期値1～nについて、勝利条件は値が2^x倍されてK以上になることである。各初期値の勝率は1/2^xで、n個の初期値の勝率を合計後nで除算する。
#includ ...
5月26日 00:39 投稿