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!)$の解法について考えます。 左から順…

最近Cまでしか解けずレートが全然上がりません...。 今回のD問題も方針自体は分かったのですが、友達の数が最も多い集団を探す関数の計算量が抑えきれずTLEしてしまいました。 解説動画でも紹介されていたUnion Findを用いた実装をしてみました。 こちらを参…

問題文 1から9までの数字のみからなる文字列Sが与えられます。 次のような条件を満たす整数の組$(i, j)(1\le i \le j \le |S|)$の総数を求めてください。 条件：$S$の$i$文字目から$j$文字目までを$10$進法の整数としてみると、この整数は$2019$の倍数である…