競技プログラミングにおける高度な数値最適化と整数論アルゴリズム
合同算術に基づく最短経路アプローチ
広範な値域における到達可能性の判定や組合せカウント、極値探索に有効な手法です。基準となる法 \(M\) を定め、各剰余類 \(0 \dots M-1\) をグラフの頂点としてモデル化します。状態 \(D[r]\) を、剰余類 \(r\) に属する値を実現するための最小コスト（または最小値）と定義します。状態間の遷移を重み付き有向辺で表現し、ダイクスト ...
5月15日 07:19 投稿