アルゴリズム解説：組合せ数学、基環木DP、および数論篩の実装
問題1：グリッド経路の組み合わせと寄与計算
本問はグリッド上の経路数と各初期値が最終結果に与える寄与度を計算する問題です。始点から終点 $(N, M)$ への移動において、右と上のみ移動可能と仮定します。各地点 $(i, j)$ から $(N, M)$ への移動経路の総数は、右への移動回数と上への移動回数の組み合わせにより $\frac{(N-i + M-j)!}{(N-i)! (M-j)!}$ で求められます。 ...
8月11日 17:39 投稿
P5298 [PKUWC2018] Minimax 解説：セグメント木マージによる木DP最適化
問題の分析
この問題は、セグメント木のマージ操作を用いて木構造上の動的計画法を最適化する手法が鍵となります。
まず、値の範囲が最大で10^9まで及ぶため、離散化（座標圧縮）が必要です。各値の出現確率を管理する必要があるため、基本的な木DPを考えます。
動的計画法の設計
dp[v][j] を頂点vにおいて、j番目に小さい値が出現する確率と定義します。遷移は以下の3 ...
6月28日 02:04 投稿