atcoder.jp 今回はダブリングと呼ばれる手法を使って解いて見ます。 drken1215.hatenablog.com 上のブログでも解説されているようにnext[i][v]を定義します。 next[i][v]: vから$2^{i}$ステップで到達できる場所 まずは$i=0$の場合を考えてnext[0][v]を初期…

C++を勉強中です。 与えられる距離行列はサイズ$N$が非常に大きい場合$N^{2}$で確保してしまうと初期化に時間がかかる。 エッジが存在する場所だけに対して情報を保持する。 そのために以下のようにノードuに対して行き先のノードvとその距離costを保持した…

atcoder.jp 幾何分布の期待値に対応しているようです。 幾何分布の期待値の計算は以下を参照して下さい。 幾何分布の確率関数からの期待値と分散の導出 | AVILEN AI Trend k回目で初めて成功する期待値を求めてNまで合計すれば計算できます。 コードは以下に…

atcoder.jp 公式の解説 www.ioi-jp.org 参考にした解説 blog.hamayanhamayan.com 上の解説を自分なりに咀嚼してみました。 $O(M!)$の解法 ぬいぐるみの初期配置が「1232132」の場合で考えてみます。 まずは計算量が$O(M!)$の解法について考えます。 左から順…